#TechToolboxTuesday : HEAPS
Reading time : 15 minutes
Day 12/30.
Heaps are one of my favorite data-structures! They might look scary in the beginning, but once you have understood the basics behind them, replication becomes easier than ever! They are also an interviewer-favorite data structure, for the same reason that they are able to test your problem solving as well as logical reasoning skills. Moreover, a lot of search algorithms such as A* and Djikstra’s algorithm use heaps under the hood for effective implementation. There are a few things I will discuss in this post with the hope that they will help you understand this data-structure better :
What is a Heap?
How to represent a Heap?
How to build a Heap?
(Since binary-heaps are the most widely used, this post will assume that “heaps” means “binary-heaps”.)
What is a Heap?
Heap is a tree-based data-structure which follows the two rules:
Each heap is a full binary tree.
Each node of the tree is in a fixed-order. There are then two types of heaps, max-heaps and min-heaps.
In a max heap, the value of each parent-node is greater than both the children.
In a min heap, the value of each parent-node is less than both the children.
Suppose there are N tourist-attractions that you want to see in a new city you visit after the lockdown ends. Each attraction has its own priority. You will want to visit the attraction with maximum priority first and then the others. The other thing that you will have to keep track of is taking the places you have seen off the priority-list, and add any attraction as needed to the priority you want. This task can be very easily executed using a heap by considering N attractions as N nodes of the tree.
How to represent a Heap?
There are two ways to represent a heap:
A logical representation : One that will help you understand the underlying algorithms and movement of nodes in and out of the heap.
A physical representation : How the heap is actually stored in the memory of the computer.
Below, I show how you can store a heap as an array without losing the logical binary-tree structure.
As you can see, this is a max-heap ( we will assume we are working with a max-heap in the rest of the article) :
Each parent node has a value larger than each of its children
It is a complete binary tree
The way you can move from the logical view to the physical view is by numbering the nodes starting at 1, and moving top to bottom from left to right. These numbers now form the indices of the heap array (starting at 1 for simplicity.)
Each node is a max-heap
Every node at index i has two children at indices : 2i and 2i + 1
The parent of a node at index i lies at index i/2
How can you build a Heap?
Now that you know what a heap is, the next big question to answer is how can you build a heap from an arbitrary array. You should always remember the two properties of the heap while doing so :
insert the element to the end of the array i.e. as the last child to maintain the complete binary tree property
Check if the inserted element is larger than the parent element, if yes, swap the parent and the child to maintain the heap property
Here is a quick video for your reference:
As mentioned, the logical representation in the form of a binary tree helps in performing & understanding operations, but all of the work happens in an array. Therefore, there are 3 important functions you can perform with a max-heap :
Get the max element
return A[1]
The pseudocode is very intuitive, you can just return the first element of the heap if A is the heap. The time complexity of this operation is obviously O(1).
Insert a new element
n = n + 1 // increase the total number of elements in the heap by 1 (n = A.length())
A[n] = x // x is the element to be inserted, inserted to the end of the array
while (parent(n) ! = 0 && A[parent[i]] < A[i] ) // you bubble-up the new element until it either reaches the top, or is smaller than its parent
swap ( A[parent[i]], A[i])) // if it is smaller than the parent, swap
i = parent[i] // change the index so that now we are at the parent and can continue bubbling up
In the worst case, the new element to be inserted is the largest in the array and so you will have to bubble up the element to the top of the tree, and hence the time complexity becomes O(log n)
Delete the maximum element
As discussed, the maximum element is at the root of the heap. To delete the last element, we can swap the first element with the last element of the array, and reduce the size of the array by 1. Then, we can perform an operation on the array to convert it into a heap, which is called the “heapify” operation. The promise of heapify is that it is a recursive operation which makes sure every node in a heap is a max-heap.
swap(A[1], A[n])
n = n-1
heapify(A, 1)
Heapify(A, i):
largest = i // perform heapify at index i, and check which is the largest element in the heap
if (left[i] <= n and A[left[i]] > A[largest]) // check if the left child exists and if its value is greater than the largest element
largest = left[i]
if (right[I] <= n and A[right[i]] > A[largest]) // check if the right child exists and if its value is greater than the largest element
largest = right[I]
if (largest == i) return; // if the root is largest, do nothing, heapify is done
swap(A[i], A[largest]) // if not, swap to put the largest element in the root
heapify(A[i], largest) // now perform heapify recursively on the root until the root is the largest element
In the worst case, the new element on the top is the smallest in the array and so you will have to trickle down the element to the bottom of the tree, and hence the time complexity becomes O(log n).
I hope you can now notice, heaps are not very scary. It takes some time, practice and some creativity to visualize the heap. Things get much easier after that! The examples above were for a max-heap, but you can easily invert them for a min-heap :)
Tomorrow, for walkthrough Wednesday, we will go over one of the common interview questions which can be solved using heaps. Looking forward!
