The heap can effeciently support basic Priority Queue operations.

In a heap, records are stored in an array such that each key is guarenteed to be larger than the keys at two other specific positions. Ordering is easy if the keys are views as being in a binary tree structure with edges from each key to the two keys known to be smaller.

Definition

A tree is heap ordered if the key in each node is larger than or equal to the keys in all of that nodes children. Equivalently, the key in each node of a heap-ordered tree is smaller than or equal to the key in that nodes parent.

Algorithms

Priority Queue algorithms on heaps all work by

1. making a simple modification that could violate the heap condition
2. traveling through the heap, and modifying as required to ensure that the heap condition is satisfied everywhere.

This called heapifying or fixing the heap.

There are two cases.

1. Traveling up: When the priority of a node is increased (or a new node is added to the bottom of the heap), you have to travel up the heap to restore the heap condition.
2. Traveling down: When the priority is decreased, we have to travel down the heap to restore the heap condition.

Traveling up

If the heap property is violated due to case 1, then the node is exchanged with its parent. After the exchange, the node is larger than both its children (old parent, old child), but may still be larger than than its new parent. This is fixed the same way, moving up the heap until reaching a node with a larger key, or the root. The code is straight forward, based on the notion that the parent of the node at position \(k\) in a heap is at position \(k/2\).

Traveling down

If the a nodes key becomes smaller than one or both of its children , then the node is exchanged with the larger of its two children. If a the heap property is still in violation at the child, then it is fixed the same way, moving down the heap until both children are smaller or the bottom is reached. The children of the node at position \(k\) are at positions \(2k\) and \(2k+1\).

References:

• Algorithms in C, Robert Sedgewick