# .css-fhxb3m{display:-webkit-box;display:-webkit-flex;display:-ms-flexbox;display:flex;-webkit-flex-direction:row;-ms-flex-direction:row;flex-direction:row;-webkit-align-items:center;-webkit-box-align:center;-ms-flex-align:center;align-items:center;}.css-vlnsew{width:2.5rem;height:2.5rem;margin-right:0.5rem;overflow:hidden;border-radius:9999px;}   Priyanka Yadav's Blog  # Heaps - An Introduction

·Oct 14, 2020·

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