Some sources claim that heaps and priority queues are the same thing. Others indicate that a priority queue is an abstract data type and a heap is an implementation of a priority queue. In reality, the distinction isn’t that important. Heaps are a great way to create a priority queue with methods that have excellent asymptotic time complexity and minimal memory overhead.

Heaps are unique in that they are logically *similar* to Binary
Trees but are stored in memory as
Arrays. First, consider a heap as a tree.

Logically, a heap is a tree that maintains the following properties:

- The node with the highest priority resides at the root
- Every node has 2 children at most
- Every layer of the tree is as full as possible
- Every node has an equal or higher priority than it’s children

There are many valid ways to organize data in a tree while maintaining these properties. This concept is best understood visually. See the image below.

A standard Binary Tree locates it’s children via
pointers stored on each node. Conversely, a heap stores all nodes in an array
and locates it’s ancestry via simple index calculations. Considering a
*non-zero based index* array and `i`

is the index of the node in question, the
following formulas are used to calculate the index of parent and children nodes
in the array.

- Parent = $\left \lfloor \frac{i}{2} \right \rfloor$
- Left Child = $2i$
- Right Child = $2i + 1$

This is a difficult concept to understand without a visual. Please see the image below.

There are actually many different heap variations. Presented above is a *Binary
Heap* which is one of the simplest. Other types of heaps vary in run times and
internal details, but they all operate similarly. An in-depth exploration of
heap implementations falls outside of scope. It would be easy to write an entire
book on the subject. To demonstrate the breadth of the topic, below is an
incomplete list of heap variants.

- 2-3 heap
- B-heap
- Beap
- Binomial heap
- Brodal queue
- d-ary heap
- Fibonacci heap
- Leaf heap
- Leftist heap
- Pairing heap
- Radix heap
- Randomized meldable heap
- Skew heap
- Soft heap
- Ternary heap
- Treap
- Weak heap

WARNINGThis section gives an account of binary heaps only. In the event that the reader has a need to implement a heap for a mission critical application, it’s highly recommended they research the topic much more thoroughly. There are many heap variants that may or may not be better suited to specialized scenarios.

## Applications

- Running Median
- Dijkstra’s Shortest Path
- Prim’s Minimum Spanning Tree
- Huffman Codes
- Any algorithm requiring repeated min/max lookups

## Asymptotic Complexity

- Insert: $O(\log n)$
- Extract: $O(\log n)$
- Reprioritize: $O(\log n)$
- Peek: $O(1)$

## Pseudo Code

```
priority_function:
item1
item2
if item1 and item2 are equal
return 0
if item1 should be before item2
return 1
if item1 should be after item2
return -1
insert:
heap_data = array containing heap items
n = number of items in the array
new_item = item to insert into the heap
heap_data[n] = new_item
bubble_up_item = new_item
n = n + 1
while bubble_up_item does NOT equal the first item in the tree:
parent = bubble_up_item's parent
if (priority_function(bubble_up_item, parent) <= 0:
exit loop and stop processing
swap bubble_up_item and parent in heap_data
bubble_up_item = parent
extract:
heap_data = array containing heap items
n = number of items in the array
return_item = heap_data[0]
n = n - 1
move last item in the array to the first item in the array
bubble_down_item = first item in array
while bubble_down_item has children:
child = child with the greatest priority
if (priority_function(bubble_up_item, parent) >= 0:
exit loop and stop processing
swap child and bubble_down_item in heap_data
bubble_down_item = child
reprioritize:
// It is assumed that the consumer updated a priority value and now needs to rearrange the heap
heap_data = array containing heap items
index = index of item to be recalculated
if (index == 0)
bubble down (see extract)
priority = priority_function(index, parent)
if(priority = 0):
return
if (priority > 0):
bubble up (see insert)
return
bubble down (see extract)
return
peek:
Return item at heap_data[0] without removing it from the array
```

## Source Code

Relevant Files:

Click here for build and run instructions