Binary Heap

A binary heap is the most common implementation of a priority queue. It is stored as a binary tree which satisfies the heap property. The heap property ensures that the node with the highest priority is always at the top of the tree where it is easy to remove. In addition, it allows for $O(\log N)$ push and pop operations. If implemented, a change_priority function can also run in $O(\log N)$ time. Unfortunately, finding the key in this time requires extra memory, and as such this feature is usually left unimplemented.

The heap property

The heap property states that a parent has higher priority than either of its two children. This property can be regenerated quickly when an item is added to the heap or the root is removed.

Operations

Push

To push an item onto the heap, place it in the first open space for a child. Then, swap it with its parent as long as it has higher priority. When this finishes, the heap property is restored. As there are $O(\log N)$ levels, the number of swaps and comparisons, and thus the running time, is $O(\log N)$ .

Pop

To pop the root off the heap, first switch it with the last element of the heap so that it may be removed without damaging anything. However, now the heap property is destroyed, but it is easy to fix. Follow the root node. While it has lower priority than either of its children, swap it with the child with higher priority. When it is bigger than both its children, the heap property is restored. As with push, $O(\log N)$ operations get executed.

Change priority

To change priority of a key, first find the key in whatever manner you like. Then change the value. If it was increased, sift it up in a manner similar to the push operation, but starting wherever it was. If it was decreased, sift it down as in the pop operation.

Run time

Operation	Complexity	Description
Push	$O(\log N)$	Pushes a key onto the heap with a certain priority
Pop	$O(\log N)$	Pops the key with highest priority off the heap
Change Priority	$O(\log N)$	Changes the priority of a key

Implementation

Because the heap is a complete binary tree at every step, it is usually implemented with an implicit data structure to save memory space. The implicit data structure in this case is a dynamic array with a node at index $c$ to have children at $2c+1$ and $2c+2$ if zero indexed and at $2c$ and $2c+1$ if one indexed. Due to the simpler child locations for one indexed arrays, a common practice is to ignore the zeroth element and act as if the array were one indexed. Because of the implicit data structure, no pointers are necessary, saving much memory space.