Algorithms and Data Structures for Programming Contests

Heaps and Priority Queues

A priority queue is a queue (a first-in-first-out (FIFO) data structure) where each element has a "priority" (a number) and elements with smaller priority values move ahead of elements with larger priority values — elements with the same priority are handled in FIFO order.
A standard queue can be implemented simply and efficiently using an array or a linked list. But this does not work well for priority queues because of the need to move elements around based on their priority.

A heap is a binary tree that satisfies two properties:
- The tree is complete, i.e., every level is full except (possibly) the last one, and every leaf on the last level is as far left as possible.
- The values are heap-ordered, i.e., every value is less than or equal to its children.
- For example, the tree below is a heap:
  
  but not this one (it is not complete):
  
  nor this one (it is not heap-ordered):
Intuitively, the heap-ordering property means that a heap is partially ordered, with smaller values near the root and larger values near the leaves — in fact, the minimum value is guaranteed to always be at the root.

Binary trees are generally implemented using nodes with pointers to children.
But because heaps are complete trees, a neat trick can be used to store all of the values directly in an array, without any nodes or pointers: store the root at index 1, the root's children at 2 and 3, etc. This is pictured below:
With this trick, every heap node is represented as an index i, and:
- parent(i) = i/2 (rounded down)
- left_child(i) = 2i
- right_child(i) = 2i + 1
(This can be modified to start at index 0, though it makes the calculations a little more complicated.)

To insert a new value into a heap:
- Add it to the end of the array (at the first available leaf position at the bottom of the tree), and increment the heap size.
- This will preserve the "complete tree" structure of the heap.
- It may violate the heap-ordering property, but this can be restored by percolating the value up: if the value is smaller than its parent, swap it with its parent and repeat.
To remove a value from a heap:
- Swap the value with the very last leaf — this preserves the "complete tree" structure — and decrement the heap size.
- Percolate the new value (at the position that was deleted) up or down, depending on how it compares with its parent and children, until heap-ordering is restored.
Both operations take time O(log n) because they travel along one path in the tree.

To maintain sequence of vertices outside the spanning tree in Prim's algorithm, or sequence of vertices to examine for Dijkstra's algorithm.
Heapsort

Algorithms and Data Structures by François Pitt is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.