Series 4: Heap

Remember those school days ?

During  school days , you typically start your day by standing in line and reciting the national anthem, school songs and the national pledge. On almost all days this line of students are organised in ascending/descending order of height. Even though this method was a little regressive in nature it was still effective. Believe me when I say this, many a jokes have been made about this, my favourite being "Remember those days when we made kids stand in the decreasing order of their insecurities?". I have to say no student was harmed in the making of this blog.

Gopher was a teacher's pet and this might be attributed to him being stationed at the start of the line. He enjoyed these school assemblies and those widely dreaded march pasts for those select occasions like sports meets, school day etc.

Just like the school assembly line there is a certain data structure which organises its contents on entry & on exit of a data element in ascending/descending order. This makes it a worthy alternative to different sorting algorithms simply because it's faster.

You guessed it right, I am talking about a Binary Heap data structure. Before we dig deeper and understand what a Binary Heap is , let us familiarise ourselves with some basic concepts.

1. A Binary Heap is simply a Binary Tree which is complete.
2. A Binary Heap is usually represented using an Array.
3. A Binary Heap can either be a Max Binary Heap or a Min Binary Heap
4. The first element in a Binary Heap is called the Root Node.
5. Each element in a Binary Heap is called a Node.
6. Each Node can have a maximum of two child nodes.
7. A Node can have no child nodes too.

What does a Binary Tree look like ?

Let us refresh our memory of how a Binary Tree looks like by looking at the following image:

You can go through a more detailed explanation about what a Binary Tree is in our blog about Binary Tree's.

Key Takeways:

• The first node (Level 0) is called a Root Node
• Every node after a Root Node is a Child Node.
• Every Child Node can also be a Parent Node.
• If a Node does not have any children then it is called a Leaf Node.

What is difference between a Max Binary Heap and a Min Binary Heap?

Max Binary Heap

Imagine the school assembly line was arranged in Descending order, this means the tallest person in the class would be standing at the front.

Similarly, in a Max Binary Heap the Root Node holds the maximum value in a given set of data elements. This means that the Array which holds the flattened Max Binary Heap will have the maximum value at the first (Array[0]) position.

Min Binary Heap

Imagine that the school assembly line was arranged in Ascending order, this means the shortest person in the class would be standing at the front.

Similarly, in a Min Binary Heap the Root Node holds the minimum value in a given set of data elements. This means that the Array which holds the flattened Min Binary Heap will have the minimum value at the first (Array[0]) position.

How is a Heap represented?

As I have mentioned earlier a Heap(Max Binary Heap / Min Binary Heap) can be represented using a 1-Dimensional Array.

How do we maintain the order in a Heap?

It is only natural to wonder how we can maintain this order of elements even while inserting/deleting  elements in to the Heap. Since both Min & Max Binary Heap's are very similar in implementation let us look Min Binary Heap to understand the inner workings of a Heap.

Inserting an element

We always insert/append an element to the end of the Binary Heap/Array and then adjust the elements/nodes of the Array/Binary Heap to incorporate the new element. This process is called Bubbling Up. As soon as you append an element to the end of the Min. Binary Heap/Array the data structure tries to find the immediate parent of the inserted element by using the formula:
parentNode = (currentElementPosition - 1)/2.

It then compares the newly inserted element with the parent element , if the parent element is greater than (lesser than in the case of Max Binary Heap) the inserted element then it swaps the two elements. This process is repeated until you reach a parent node which doesn't satisfy the above condition.

Extracting the element with minimum value

As you know the Root Node is the element with the minimum value in a Min Binary Heap, therefore we just have to extract the Root Node at any given point of time to get the minimum value in a Min Binary Heap. Once this happens we need to find a new root node which requires a total reshuffle of the heap. For this purpose, we move the numbers with higher value to the bottom of the heap and the numbers with lower values to the top of the heap. Let's call this process the Bubbling Down Process.

As soon as you remove the Root Node, we take the last element in the Min Binary Heap/Array and substitute it as the new Root Node. We then find the new Child Nodes using the formula:
* Left Child Node = 2 * currentNodePosition + 1
* Right Child Node = 2 * currentNodePosition + 2

Once we know the child nodes we compare the Current Node/Parent Node with each of the child node values. We then swap the nodes if the any of the child node values are lesser than the Parent Node (greater than the Parent Node for Max Binary Heap). This process is continued till all the nodes are in the right positon.

How would this look like in code ?

Step 1: Package Management & type definition

Let us create two variables -

1. One will be used to store the integer array and the index in itself ,let us call it Node
2. The other will be an integer array, let us call it MinHeap

package main

import (
	"fmt"
	"time"
	"math/rand"
	"math"
	"strings"
)

type Node struct {
	heap  *MinHeap
	index int
}

type MinHeap struct {
	arr []int
}

Step 2: Initialisation

In the previous step, we specified how we will store the information, now we need to figure out a way to create the same,i.e, a function to initialise the Min Binary Heap.

func NewMinHeap(values ...int) *MinHeap {
	h := &MinHeap{
		arr: append([]int{}, values...),
	}

	for i := len(h.arr)/2 - 1; i >= 0; i-- {
		h.bubbleDown(i)
	}

	return h
}

Step 3: Insert an Element

Let us now write a function which will be responsible for appending a new element to the Min Binary Heap.

func (h *MinHeap) Insert(value int) {
	h.arr = append(h.arr, value)
	h.bubbleUp(len(h.arr) - 1)
}

Step 4: Bubble up the new Element

Now that the element has been appended we will need to reshuffle the Heap so that the new element can be moved to the correct position in the Heap.If the element is already in the correct position then we will not rearrange the Heap.

func (h *MinHeap) bubbleUp(idx int) {
	for {
		parentIdx := (idx - 1) / 2
		if idx == 0 || h.arr[parentIdx] <= h.arr[idx] {
			break
		}
		h.arr[idx], h.arr[parentIdx] = h.arr[parentIdx], h.arr[idx]
		idx = parentIdx
	}
}

Step 5: Remove the  element with minimum value

The element with minimum value is the root element.Simply extracting the root element will provide you with the current minimum value.

func (h *MinHeap) extractMin() (int, bool) {
	if len(h.arr) == 0 {
		return 0, false
	}
	val := h.arr[0]
	h.arr[0], h.arr[len(h.arr)-1] = h.arr[len(h.arr)-1], h.arr[0]
	h.arr = h.arr[:len(h.arr)-1]
	h.bubbleDown(0)
	return val, true
}

Step 6: Perform Bubble Down operation

Once the Root Node is extracted, we need to find a new Root Node/ new minimum value.For this purpose we will be reshuffling the entire Heap again.

func (h *MinHeap) bubbleDown(idx int) {
	for {
		// pick child to swap (smaller one)
		childIdx := idx*2 + 1                       // left child
		if childIdx >= len(h.arr) || childIdx < 0 { // <0 int overflow
			break
		}
		rightIdx := childIdx + 1
		if rightIdx < len(h.arr) && h.arr[childIdx] >= h.arr[rightIdx] {
			childIdx = rightIdx
		}
		// swap
		if h.arr[childIdx] >= h.arr[idx] {
			break
		}
		h.arr[idx], h.arr[childIdx] = h.arr[childIdx], h.arr[idx]
		idx = childIdx
	}
}

Step 7: Print the Heap

In order to print the Heap as we perform various operations on it, we have create a printHeap() method and some auxilliary functions to help with this process.

func (h *MinHeap) PrintHeap() {
	for i := 0; i < len(h.arr); i++ {
		node := h.nodeAt(i)
		// left-side whitespaces
		if leftChild := node.LeftChild(); leftChild != nil {
			if node.isRightChild() {
				fmt.Print(strings.Repeat("-", leftChild.calcPrintWidth()))
			} else {
				fmt.Print(strings.Repeat(" ", leftChild.calcPrintWidth()))
			}
		}
		// node value
		fmt.Printf(" %d ", node.Value())
		// right-side whitespaces
		if rightChild := node.RightChild(); rightChild != nil {
			if i == 0 || node.isRightChild() {
				fmt.Print(strings.Repeat(" ", rightChild.calcPrintWidth()))
			} else {
				fmt.Print(strings.Repeat("-", rightChild.calcPrintWidth()))
			}
		}
		if node.isRightMost() {
			if i == len(h.arr)-1 && !node.isRightChild() {
				if parent := node.Parent(); parent != nil {
					if vw := parent.calcWidth(); vw > 0 {
						fmt.Print(strings.Repeat("-", vw/2))
						fmt.Print("+")
					}
				}
			}
			fmt.Println()
		} else {
			if rightParent := node.findRightParent(); rightParent != nil {
				if vw := rightParent.calcWidth(); vw > 0 {
					if node.isRightChild() {
						fmt.Print(strings.Repeat(" ", vw))
					} else {
						fmt.Print(strings.Repeat("-", vw/2))
						fmt.Print("+")
						fmt.Print(strings.Repeat("-", (vw-1)/2))
					}
				}
			}
		}
	}
}

Please find the complete working code for Min Binary Heap at the following location:

Let's talk performance now!

The only two complexities in terms of performance that we care about is the time taken to  insert/remove a new Node  from the Min Binary Heap(Time Complexity) and how big/long the Binary Heap actually is  (Space Complexity).

Time Complexity

1. Deleting an Element : Since this operation involves returning the Root Node of the Array/Heap and also reshuffling the entire Heap the Time Complexity of this operation is O(log(N)).
2. Insert a New Element : Since this operation involves appending the Node to the end of the Array/Heap and then reshffling the entire Heap the Time Complexity of this operation is O(log(N)).
3. Extract Minimum Value : Since this operation involves returning the Root Node the Time Complexity of this operation is O(1) .

Space Complexity

If there are N Nodes that needs to be stored then we need a Binary Heap of size N. Therefore the Space Complexity for a Binary Heap is termed as Linear Space Complexity and is denoted as O(N).

Go provides Heap as an in-built package and all of the operations that we discussed in the earlier blog is available for any type that implements the heap interface. You can find more details here: https://pkg.go.dev/container/heap

In the next post we will see some real world examples where the concept of Binary Heap is used.