What is a Heap?

A heap is, in essence, a special version of a tree; it adheres to the heap property, and exhibits binary completeness. While there are many forms of Heaps, they are most commonly implemented as binary-heaps.

Binary-heaps are usually seen in two forms: Min-Heaps and Max-Heaps

Assumptions

Knowledge of <a href="https://www.devmaking.com/learn/algorithms/big-o-notation/" style="color:inherit;" target="_blank">Big-O notation</a>
Familiarity with Tree-like data structures

The Heap Property

The definition of the heap property depends on whether the heap is a Min-Heap or a Max-Heap. In the case of a Min-Heap, for any given node, all children must contain values larger than itself. The reverse is true for a Max-Heap, where all children must contain values smaller than itself.

An important consideration when deciding on a heap is knowing that there is no-implied order of values; the only guarantee is that each level contains larger (Min-Heap) or smaller (Max-Heap) values than the previous.

Binary Completeness

A tree where every level (except the lowest) is completely filled with nodes. In the case of the lowest level, the nodes must be filled in from left to right.

Heap Performance

The following are common methods that a binary heap implementation would include, and their respective complexities. Each of these methods will be looked at in more detail shortly!

Method	Complexity
FindMin	O(1)
Insert	O(log N)
DeleteMin	O(log N)

Heap Methods (Min-Heap)

> While these methods will all be shown through the lens of a Min-Heap, only minor changes are needed to implement the Max-Heap counterparts!

// Our data structure:
int[] data;
int currentSize;

FindMin

Finding the minimum value in a Min-Heap is simple: the root value! As long as the heap property is being met, the root will always be the minimum value in the tree.

/* pseudocode */

/*Assumes the heap is non-empty.
    An IsEmpty method can help check.*/
 int FindMin()
 {
   return data[0];
 }

If using a Max-Heap, the root would be the maximum value.

Insert

Inserting a value into a tree may sound straightforward, but there is a bit of a catch when it comes to heaps; we need to make sure that heap order is still valid!

Usually, min-heap insertion is handled using the swim approach:

Add the value to the end of the array
If the parent value is larger than the new value, swap the two.
Repeat step 2 until the new number's parent is smaller.

> Swim is often used interchangeably with 'percolate-up', 'bubble-up', or 'sift-up'

/* pseudocode */

/* Assumes a non-full array! */

void Insert(int value)
 {
     // 1. Insert at the end of the array:
   currentSize++;
   data[currentSize - 1] = value;
   // Put it in heap order:
   Swim(currentSize - 1);
 }

/* helper method for insertions: */
void Swim(int index)
 {
   // If we're not at the root index..
   if(index != 0)
     // ..Get the parent:
     int parent = (index - 1) / 2;
     // 2. If the parent is larger, swap them:
     if(data[parent] &gt; data[index])
         int tmp = data[parent];
           data[parent]  = data[index];
           data[index] = tmp;
           // 3. Repeat step 2 until the parent is smaller:
           Swim(parent);
 }

DeleteMin

To perform a deletion, we need to follow the sink approach:

Replace the root value with the last value (and remove the last).
If the current value is greater than any of the children, swap with the smaller child.
Repeat step 2 until heap order is restored.

/* pseudocode */

/* Assumes a non-empty array! */

void DeleteMin()
 {
   // 1. Replace the root value with the last value:
   data[0] = data[currentSize - 1];
   // Remove the last value (decrease size):
   currentSize--;
   // Sink the value down:
   if (currentSize &gt; 0)
     Sink(0);
 }

void Sink(int index)
 {
   int leftChild = (index * 2) + 1;
   int rightChild = (index * 2) + 2;
   // Automatically set minimum to the left to reduce complexity:
   int minumum = leftChild;
   
   // Check bounds:
   if(rightChild &gt;= currentSize)
     // If the left AND the right children are out of bounds, exit.
       if(leftChild &gt;= currentSize)
           return;
   // If the left is larger than the right child:
   else if data[leftChild] &gt; data[rightChild]
         minimum = rightChild;
   
   // If the index is out of place with the minimum:
   if(data[index] &gt; data[minimum])
     // Swap:
     temp = data[minimum];
     data[minimum] = data[index];
     data[index] = temp;
       // Continue sinking:
       Sink(minimum);
   
   // (else) we're in heap-order!
 }

Heap vs. Binary Search Tree (BST)

Unlike binary heaps, <a href="https://www.devmaking.com/learn/data-structures/binary-search-tree/" style="color:inherit;" target="_blank">binary search trees</a> are ordered so that every element to the right of a given node is larger, while every element to the left is smaller. This is an important difference, because this means that a binary search tree does not exhibit binary completeness!

There are certain times, though, when using a BST is better than using a heap; if you need an arbitrary node from the tree at any moment, a BST is better suited for the job with O(log n) complexity.

However, if you're only interested in getting the smallest (or largest) value in a tree, then a binary heap is the best bet with an O(1) complexity! When implementing a priority queue, being able to find the smallest value at any given moment is essential, and can help speed up greedy algorithms such as Dijkstra's Theorem, and other shortest-path algorithms.

> Challenge: write your own Max-Heap, then refactor it to use an explicit data structure instead of an array!