  # Heaps - An Introduction

Subscribe to my newsletter and never miss my upcoming articles

Heaps are advanced data structures and are mostly implemented using priority queues. They can be thought of as a tree-based structure, in which the tree is a complete binary tree.

( A complete binary tree is a tree in which every other node other than the leaves have two children ) The 2 main characteristics of Heaps are

• It should be a complete binary tree.
• Nodes must be according to the Heap order property.

The 2 heap order priorities are 1. Max heap property - In a max-heap, the value of the root node should be the greatest among all the value of all of its children. The same property should be recursively true for all the sub-trees.

2. Min heap property - In a min-heap, the value of the root node should be the smallest among all the values of all of its children. The same property should be recursively true for all the sub-trees.

### Applications of Heaps

1. Heap Sort uses Binary Heap to sort an array in `O(N log N)` time.
2. Heaps are also used to implement Priority Queues.
3. Priority queues, in turn, are used to solve graph algorithms and array related questions.

### Representation of a Binary Heap

A binary heap is generally represented using an array, by level order traversal. The root element is always the first element of the array. or a node, present at index i -

• Its `parent` can be found at - `heap[(i-1)/2]`
• Its `left child node` can be found at - `heap[(2*i)+1]`
• Its `right child node` can be found at - `heap[(2*i)+2]`

### Operations and Time Complexities of a Heap

1. `heapify()` - heapify operation is called when the binary heap violates the heap property. heapify rearranges the heap in such a way, that it becomes valid again. This takes `O(log N)` time.

2. `getMin()` or `getMax()` - Returning the root node value of a min/max heap in `O(1)` time.

3. `extractMin()` or `extractMax()` - Removing the root node of a min/max heap. This takes `O(log N)` time because heapify operation is called, to maintain the heap property, after removing the root node.

4. `insert()`: Inserting a new key takes `O(log N)` time. We add the new key at the end of the max/min-heap. If the key violates the heap property, we traverse up and fix the tree.

5. `decreaseKey()`: Decreases the value of a key in a heap. If the decreased value violates the heap property, we traverse up and fix the tree. This takes `O(log N)` time.

6. `increaseKey()`: Increases the value of a key in a heap. If the increased value violates the heap property, we traverse up and fix the tree. This takes `O(log N)` time.

7. `delete()`: Deleting a key also takes `O(log N)` time.

For min-heap, replace the value to be deleted with -INFINITY. Doing so, the value at the root node will now become -INFINITY. Then call `extractMin()`.

For max-heap, replace the value to be deleted with +INFINITY. Doing so, the value at the root node will now become +INFINITY. Then call `extractMax()`.

### Implementing a min-heap using array

First we define a class for the heap.

``````class MinHeap
{
int *mh;   // pointer to the array of heap elements
int maximum_size;  // maximum size of the array or maximum number of heap nodes
int current_size;  // current size of the array or current number of heap nodes
}
``````

Constructor to initialize the heap - we would only be needing the maximum_size of the array as a parameter

`````` MinHeap::MinHeap(int size)
{
current_size = 0;
maximum_size = size;
mh = new int[size];
}
``````

Functions to return the parent, left, and right child node.

``````     int parent(int i) { return (i-1)/2; }

int left(int i) { return (2*i + 1); }

int right(int i) { return (2*i + 2); }
``````

Now, to insert a new key -

1. First insert the new key at the end.
2. Traverse up to fix the violated min-heap property if any.
``````void MinHeap::insertKey(int k)
{
if (current_size == maximum_size)
{
cout << "Overflow : Cannot insert more nodes";
return;
}

// First insert the new key at the end
current_size++;
int i = current_size - 1;
mh[i] = k;

// Traverse up & fix the min heap property if it is violated
while (i != 0 && mh[parent(i)] > mh[i])
{
swap(&mh[i], &mh[parent(i)]);
i = parent(i);
}
}
``````

Now to decrease key.

1. Decrease the key
2. Traverse up & fix the min-heap property if it is violated
``````void MinHeap::decreaseKey(int i, int new_val)
{

// Decrease the key
mh[i] = new_val;

// Traverse up & fix the min-heap property if it is violated
while (i != 0 && mh[parent(i)] > mh[i])
{
swap(&mh[i], &mh[parent(i)]);
i = parent(i);
}
}
``````

Now, `heapify` method - To heapify a subtree with the root at given index i. The method assumes that the subtrees are already heapified.

``````void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < current_size && mh[l] < mh[i])
smallest = l;
if (r < current_size && mh[r] < mh[smallest])
smallest = r;
if (smallest != i)
{
swap(&mh[i], &mh[smallest]);
MinHeapify(smallest);
}
}
``````

Now, to extract the minimum/root node.

• Remove the root node.
• Replace the root node value with the last node value.
• Heapify the tree from the root.
``````int MinHeap::extractMin()
{
if (current_size <= 0)
return INT_MAX;
if (current_size == 1)
{
current_size--;
return mh;
}

// Remove the root node.
int root = mh;

// Replace the root node value with the last node value.
mh = mh[current_size-1];
current_size--;

// Heapify the tree from the root.
MinHeapify(0);

return root;
}
``````

Now, to delete a key.

• Replace the value of the key with INT_MIN.
• Extract the min/root node.
``````void MinHeap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}
``````

You can find the entire code here.

Subscribe to the newsletter to read more blogs on data structures and algorithms!

References -

educative.io/edpresso/what-is-a-heap

geeksforgeeks.org/heap-data-structure