Priority Queues/Heap

Notes

Heap

The concept behind the heap is to balance the tradeoffs of the unsorted and the sorted priority queue. Rather than having to choose O(1) add and O(N) removal, or O(N) add and O(1) removal, the heap allows O(log N) insertion and removal both.

The heap order is defined as follows:

• Root node must be the smallest key value
• Child nodes must have greater key values than parent nodes

Heaps T must have minimal height

Heap T must be complete

• Left and right subtrees cannot differ by more than 1 hierarchical level
• Packing in the heap tree from left to right, top to bottom
• Height = floor(log(N))

Heap Add

Add to the next spot in the tree

• We pack in the heap tree from left to right, top to bottom
• We insert new nodes at the very bottom of the tree, last row, filling to the right.
• After we insert a new node, the heap tree may violate heap order property (HOP)
• Heap post-add procedure: up-heap bubbling

if the position of the new node is not root:
    compare p to p's parent q
    if k_p < k_q:
        swap p and q
        re-apply up-heap bubbling to parent

Heap Remove

Remove root of the tree (minimum item in tree)

• Minimum item is always at root, so removing it is always an O(1) operation
• Rearranging tree after that to preserve heap order property is not an O(1) operation, it's an O(log N) operation
• Root node is removed, replaced with last node in tree (right-most node of last layer)
• Heap post-remove procedure: down-heap bubbling

if T has one node (root), we are done
if one child, let c be child of p
if two children, let c be smaller of p's children
if k_p > k_c, swap to restore heap order property and continue to apply down tree