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

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Heaps_01.png" alt="min-heap and max-heap comparison" style="max-width:95%;"> </div>

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.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Heaps_02.png" alt="binary completeness diagram" style="max-width:95%;"> </div>

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

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Heaps_03.png" alt="inserting 2 into a min-heap" style="max-width:95%;"> </div>

```
/* 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] > 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.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/datastructures/Heaps_04.png" alt="removing the min from a min-heap" style="max-width:95%;"> </div>

```
/* 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 > 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 >= currentSize)
// If the left AND the right children are out of bounds, exit.
if(leftChild >= currentSize)
return;
// If the left is larger than the right child:
else if data[leftChild] > data[rightChild]
minimum = rightChild;
// If the index is out of place with the minimum:
if(data[index] > 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!