Heap and Heap Sort

Heap

• Definition

  A complete binary tree in which parent node is always less/greater (min/max heap) or equal (if allow overlapped values) than its children

• Logically a binary complete tree

• physically an array

  • find parent/children by arithmetic calculation of indices

    • given the node \(i\)

    • the index of the parent node is \((i-1)/2\)

    • the indices of the children nodes are left: \(i*2+1\) and right: \(i*2+2\)

• type

  • max heap - root being the greatest value

  • min heap - root being the smallest value

• behaviors

  • insert

    • insert at the end

    • swap with its parent if it violate the rule (percolate up)

    • keep checking all ancestors till the root is reached

  • remove

    • remove the root by overwriting it using the last element

    • swap the parent node with its least/greatest child starting from the root until the leaf node is reached (percolate down)

  • percolate up/down

    • move one element up/down in an existing heap

  • Heap creation

    1. Insert element one by one to a new heap. \(\Theta(n \log n)\)

    2. Heapify: Percolate down all internal nodes in the order from the last to the root \(\Theta(n)\)

       • repeatedly percolate from the index \(size/2-1\) to \(0\)

A max heap (tree form)

A max heap (array form)

Applications

• Heap sort

• Priority queue

Visualization

• http://www.cs.usfca.edu/~galles/visualization/Heap.html

• https://visualgo.net/en/heap

Priority queue

• Not really a queue or stack because the dequeue order is not related to the enqueue order

• any in min/max out

• behaviors mostly same as a queue

  • enqueue

  • dequeue

  • peek

  • isEmpty

  • length

• Implementations

  • heap best

  • sorted array, sorted insert to insert

  • sorted linked-list, sorted insert to insert