# Heaps - An Introduction

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

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

- Heap Sort uses Binary Heap to sort an array in
`O(N log N)`

time. - Heaps are also used to implement Priority Queues.
- 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

`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.`getMin()`

or`getMax()`

- Returning the root node value of a min/max heap in`O(1)`

time.`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.`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.`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.`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.`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 -

- First insert the new key at the end.
- 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.

- Decrease the key
- 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[0];
}
// Remove the root node.
int root = mh[0];
// Replace the root node value with the last node value.
mh[0] = 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 -