Heap

Introduction

The array is efficient but the sorting is an expensive procedure. We’ve also used priority queue in simulation process, this queue doesn’t work on the FIFO rule but on the importance/priority of event. We implemented priority queue through array, but removal or addition of element in the array leads to the left or right shifting, which isn’t efficient. To overcome this, we use heap. In this article, we’ll learn about MinHeap and MaxHeap. We’ll implement complete binary tree through heap. Next, we’ll also perform insertion and deletion in MinHeap, the same method will also be implemented on MaxHeap. So, if you understand one, solving other won’t be problem to you.

The definition of heap is that it’s a complete binary tree that conforms to the heap order.

MinHeap

The heap order is a property that states that in a (min) heap for every node X, the key in the parent is smaller than (or equal to) the key in X. In other words, the parent node has key smaller than or equal to both of its children nodes.

Value of every node is greater than its parent.

We implement heap with complete binary tree, the image you see is not BST but a complete binary tree.

Figure-2 isn’t MinHeap, it’s just a complete binary tree.

MaxHeap

This is opposite to MinHeap. Every parent node is greater than its children nodes.

Insertion in a Heap

First have a look at the existing heap in figure-4. We’re well aware of the property of complete binary tree. If the node is at position i, then its children will be at positions 2i and 2i+1. For the node at position i, its parent will be at position i/2.

Let’s insert a new node 14 at position 11 in the MinHeap.

This is still a complete binary tree, because no hole is created in the array and there is no wastage of memory.

Procedure of Insertion

We won’t directly use the node for its insertion in MinHeap. Rather, we’ll make a hole in place of node, after fixing its position in the tree, we’ll place node in the place of hole.

Have a look at figure-6, that’s what we’re going to achieve.

We’ll compare the new node with parent node through i/2, while the new node is at position i. If it’s less than its parent then swap their positions. See figure-7.

Array for the binary tree in figure-7 is shown in figure-8.

Again, we’ll go through the comparison procedure of the new node with the parent node. This procedure continues until we don’t get the parent which is less than the new node.

After we’ve found the right position for the hole, we’ll finally insert the value in it, which is 14 in our case.

Figure-10: Inserting new value in a heap

Make sure you don’t get confused about different types of the binary tree.

Full Binary Tree: Every node has 0 or 2 children. Complete Binary Tree: Every level, except possible the last, is completely filled and all nodes are as left as possible. Perfect Binary Tree: All nodes have 2 children.

Let’s insert a new node 16 into the same MinHeap.

Figure-11: Inserting new value in a heap

Figure-12: Inserting new value in a heap

Figure-13: Inserting new value in a heap

Now, finally insert the value in place of hole.

Deleting from a Min-Heap (deleteMin)

Finding the minimum is easy; it’s at the top of the heap, 13 in our case.

Coming back to the deletion, it’s necessary to understand that deletion (or removal) causes a hole which needs to be filled.

After this, we’ll compare the children of hole with each other, the smaller one will be swapped with the parent/hole. As 14 < 16, so, 14 will be swapped with hole.