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

• Try our Binary Heap Visualizer to step through heap operations in both tree and array views.
• 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