Data structure — Heap

In this blog we’re going to take a look at Heap data structure.

Table of contents

1. Array representation of binary tree
2. Complete binary tree
3. Heap
4. Insert (in a Max Heap)
5. Delete (in a Max Heap)
6. Heap sort (in a Max Heap)
7. Heapify
8. Priority Queue
9. References

1. Array representation of Binary tree

A binary tree is a tree where each node can have 2 elements at most. One way to represent a binary tree is using an array.

In the array, every element at position i represents a node in the binary tree.

• Position of any given node — i
• Position of left child of the node — 2 * i
• Position of right child of the node — (2 * i) + 1

Note: I have used the term position since i is 1-indexed.

Arrows show the left and right children of the node.

2. Complete binary tree

A full binary tree is a tree where all levels are full. To add another element, we’d need to increase the height of the binary tree.

A complete binary tree is a binary tree in which all levels are full. The last level may not be full. In that case, the last level is filled from left to right. Every full binary tree is a complete binary tree but not vice-versa.

In the array representation of a complete binary tree, there are no empty slots.

An incomplete binary tree is a binary tree where intermediate levels may not have all the elements. There may be empty slots in the array representation of the incomplete binary tree.

The incomplete binary tree has empty slots since the children of node 2 are missing.

3. Heap

A heap is a complete binary tree.

Types of Heap

1. Max Heap — Every parent node is greater than all its children.
2. Min Heap — Every parent node is less than all its children.

Max Heap and Min Heap

4. Insert (in a Max Heap)

To insert a node, we insert the node at the end of the array. Then we repeatedly compare it with the parent node and swap the nodes if the child is greater than the parent.

Time complexity — O(logN) (Equal to the height of the Heap)

Insertion of a node in Max Heap

5. Delete (in a Max Heap)

While deleting a node, we can only delete the root node from a Heap. The last node takes the place of the root node. Now we repeatedly compare this node with its children and swap it with the child whose value is greater.

Time complexity — O(logN) (Equal to the height of the Heap)

Deletion of a node in a Max Heap.

6. Heap sort (in a Max Heap)

Every time we delete a node from the Heap, we delete the largest node. If we start placing the deleted nodes in an array in the reverse order, we’d get a sorted array as a result.

We remove N nodes. Time to remove each node is logN . Time complexity of Heap sort — O(NlogN) .

With Heap sort, we can do in-place sorting. When a node is removed, it is replaced by the last node in the array. Simply keep placing the removed node at the end of the array.

7. Heapify

Heapify is the process of creating a Heap from a given binary tree.

We start at the last node in the array, and adjust it downwards (like we did when deleting a node). We do this for every node starting at the last node in the array. As a result, we get a Heap in the end.

Time complexity — O(N)

Time complexity if we would have created a Heap using N insert operations — O(NlogN) .

8. Priority Queue

Queue = FIFO (First in first out)

Priority Queue = FIFO with priorities.

In a Max Heap, larger number has higher priority. In a Min Heap, smaller number has higher priority.

To implement Priority Queue, Heap is the best Data structure.

Time complexity to find and delete a node from an array — O(N) .

Time complexity to delete a node from a Heap — O(logN) .

9. References

Abdul Bari sir’s lecture 2.6.3 on YouTube.

If you find any mistakes, feel free to let me know in the comments.