# Heap

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:

1. The node with the highest priority resides at the root
2. Every node has 2 children at most
3. Every layer of the tree is as full as possible
4. 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
• Randomized meldable heap
• Skew heap
• Soft heap
• Ternary heap
• Treap
• Weak heap

WARNING This 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.

## 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


Full Repo

Relevant Files: