Hi, everyone today will be talking about Heaps. I watched a Youtube video about developing heaps using GoLang and it was very interesting. We are trying to learn the basic concepts about heaps like inserting and extracting data from heaps and also the time complexity of heaps. Finally we will be developing a heap data structure from scratch using GoLang.
Heaps are a very interesting data structure, we think it is like a tree structure but actually, it is an array. So it is interesting to know how it works and how to implement one because it will be helpful in algorithms.
The heap data structure was originally introduced as a part of the algorithm called heap sort but the data structure introduced there was also important for other applications such as priority queues, Selection algorithms, Graph Algorithms, etc. Heap sorts are great for implementing priority queues. Because in Normal queues we do FIFO — First, in first out but in Priority Queues, we need to serve the highest priority first.
What is Heap?
Heap is a data structure that can be expressed as a complete binary tree. A complete tree means that all the levels in the tree are full except for the lowest level where some nodes can be empty but all its nodes are to the left.
The above image shows a Binary heap, as you can see there all the levels are full except the lowest level and this is a binary heap because of nodes up to two children.
In the case of the max heaps, the largest key will be held in the root and for all the nodes in the tree, every parent will have a higher key than its children. Max heap will be useful when we need to repeatedly remove the largest key in the tree (as Priority queues) because we already know that the largest key will be on the root.
So getting the largest key will be so fast regardless of the size of the heap. Opposite the max heap is the min-heap where the smallest key is the root so in a min-heap each parent will have a smaller key than their children. Here we are going to talk about max heaps because basically min-heap is the opposite of max heap.
Heaps as Array?
At the beginning of this post, I told you that we can consider heaps as arrays, not trees. Let's see why is that, heaps can be visualized as a tree but actually behind the scenes the keys are stored as an array where each node of the tree corresponds to an index of that array.
As you can see in the above image we can combine each level and perform an array so the root will be the first element. Lets’ consider an integer array of x. So the root will be x[0]. And its child nodes which are 16 and 48 in the above case will be x[1] and x[2]. If we look at the first child node of the root which is x[1] and its child nodes are 14 and 8 we can represent them as x[3] and x[4]. If you know mathematical induction we can see that there is a pattern in which you can get the left node and right node from a particular parent by using the below formulas.
Left Node — 2*index +1
Right Node — 2*index +2
Insert keys to Max Heap
Okay now, let’s see how we can insert the keys into a heap. Whenever we are performing an insert we are going to add the new key to the last index of the array. After that, we need to rearrange the nodes to preserve the max heap property which is to keep the parent key larger than the child nodes.
So what we do is rearrange the indices to preserve heap property. So compare the newly added child key with its parent and swap if the child key is larger than its parent so that we do that process until the heap property is preserved. This process is called Heapify.
Extract Keys from Max Heap
Getting the largest element from the max heap is not a problem because basically the largest element in the max heap is the root element. After extracting the root element you need to fix the heap. So let’s see how we do it.
So to fix the heap after extracting its root, what we do is replace the root with the last index of our heap ( last index of our array) in the above image which is 34. So after replacing it, we will consider the root element and its two children, we will compare what is the largest element between those two children and replace that with the root.
In the above image, we will consider 16 and 50. 50 is the largest element so we swap 50 and 34. Again we will check what is the largest element of nodes which is 34,48 and 20. Among them, 48 is the largest element so we will swap that with the 34 that we will do that process until there are no swaps needed.
Time Complexity of Heap
Basically, if we think about heaps the complexity of the heap depends on how much time it will take to do the Heapify process ( which is to preserve the heap structure). That will depend on the height of the tree. If we think the height of the tree is h and it has n number of nodes. Then the time complexity of the heap is O(h). We can simplify it to O(log n)
Let's try to think how O(h) is equal to (log n).
Binary heap and it has n number of nodes, if we start from the bottom level it would have n/2 and the next level n/4 and the next level n/8 and so on… If we think of a 3-level tree the bottom level will have 4 elements and 2nd level have 2 elements and the root only have one element.
So to come to the bottom level the complexity is O(h) which is 2. So as log2(4) = 2 and come to the 2nd level the complexity is 2 which is O(h) and log2(2)=1. Refer to this for how to calculate tree height. So insert and extract from the heap O(log n)
Let's get hands dirty 👋
Let's try to build a Max heap using GoLang and run it. (In Go language public and private methods are defined whether the first letter of the method is Upper Case — public or Lower case — private).
Let me add the whole source code below and explain the methods one by one.
https://gist.github.com/maneeshaindrachapa/1facf01e9dd712166029e11d1df87c4e
First, we create a MaxHeap struct (Go structs are typed collections of fields that are useful for grouping data together to form records.) In that struct, we are having a slice that goes by the name array(Go Slices are a key data type in Go, giving a more powerful interface to sequences than arrays.)
We need a few supporting functions such as right to return the right child to a parent. left to return the left child of a parent. parent to return the parent. swap to swap the elements. We are using the above-discussed mathematical functions to get the left and right child from a parent.
In the Insert the method we will try to insert a new key to our MaxHeap So we will append the new value to the array. ( append will add the key to the end of the array). Next, we need to do the maxHeapifyUpprocess to preserve the heap data structure.
Then maxHeapifyUp what happens is it will check whether its value is greater than the value of its parent and if it is greater it will swap with the parent node and again check if will be greater than its new parent node this process will happen until h.array[parent(index)] < h.array[index] its value is not greater than its parent node value.
In the Extract method what we do is return the parent node which is the first element of the array and then we will set the last element of our array to the first element of our array and remove the last element from the array which is not set as the root element ( because we don’t need duplicates).
Then we need to do the maxHeapifyDown process to preserve the heap data structure. In maxHeapifyDown the process what we do is get the left and right child of the root and get the maximum value and swap those values until h.array[index] < h.array[childToCompare] We will get childtoCompare by getting the max value from the left and right children.
So that is the code. I hope you got an idea about Heap data structure and how to implement Heap data structure using Go Lang.
References
https://junminlee3.medium.com/
https://www.youtube.com/watch?v=3DYIgTC4T1o&ab_channel=JunminLee
Also published here.