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.

Heap

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.

Heap Indexing

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

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.

Applications

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

Full Repo

Relevant Files:

Click here for build and run instructions