Priority Queue

Maintains a set of elements along with a numeric key value for each element. Supports:

• insert
• decreaseKey
• deleteMin
• makeQueue (also known as heapify)

Binary Tree

The canonical way of implementing a priority queue is by using Trees. Here, an ordering is enforced where the value of each vertex needs to be ≤ that of its children.
insert

• Place a new element at the bottom of the tree and set it bubble up
• If parent is larger, swap the two and repeat
• Height of the binary tree is $\log (V)$ so this many swaps can be performed at most decreaseKey
• Same as insert
• Just a bubble up from the current position
• We store and update a handle that tells the location of each vertex’s dist value in the tree deleteMin
• Return the root value
• To fix the tree, take a vertex in the last later, place it at the root and let it sift down
• Also $O(\log V)$ heapify
• Also known as Floyd’s heap construction, this actually runs in $O(V)$ time rather than using the typical insert. This is not the bottleneck though.