Golang: Heap data structure

Heap is a completely binary tree and the root node has the smallest/largest value. It can also represented in the form of an array. When we use heap data structure in Golang, we can use the container/heap package by implementing the heap.Interface. When we build heap data structure from scratch, sift down operation is more efficient than sift up operation. You can check more details in this story.

Heap data structure summary card

Table of Contents
· What is Heap?
  ∘ A complete binary tree
  ∘ Heap property
· Array Representation of Binary Heap
· Two Ways to Implement Heap
  · Method 1: Use Heap Package - container/heap
    ∘ Min Heap
    ∘ Max Heap
  · Method 2: Implement Heap Data Structure from scratch
    ∘ Sift Down vs. Sift Up
    ∘ Why Sift Down is More Efficient?
    ∘ MinHeap
    ∘ MaxHeap

What is Heap?

A complete binary tree

A special binary tree in which all its levels are completely filled up except possibly the last one and all nodes are filled from left to right.

full vs. complete binary tree

Heap property

• Min heap: the value of child nodes is greater than or equal to the value of its parent. The root node has the minimum value.
• Max heap: the value of child nodes is smaller than or equal to the value of its parent. The root node has the maximum value.

min heap vs. max heap

Array Representation of Binary Heap

• Heap can be represented in the form of an array .
• Heap is not a sorted array.

╔═══════════════════╦════════════════════════╗
║ vertex            ║ index                  ║
╠═══════════════════╬════════════════════════╣
║ root              ║ 0                      ║ 
║ current           ║ i                      ║
║ parent            ║ (i - 1) / 2            ║
║ left child        ║ 2*i + 1                ║
║ right child       ║ 2*i + 2                ║
║ the last non-leaf ║ (array length - 2) / 2 ║            ╚═══════════════════╩════════════════════════╝

array representation of binary heap

Two Ways to Implement Heap

Method 1: Use Heap Package - container/heap

Implement the heap.Interface to use the heap operations in the heap package.

// heap.Interface
type Interface interface {
	sort.Interface
	Push(x interface{}) // add x as element Len()
	Pop() interface{}   // remove and return element Len() - 1.
}

The heap.Interface embeds sort.Interface into its signature.

// sort.Interface
type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
}

Therefore, we need to create a custom type that requires to contain Len, Less, Swap, Push and Pop methods.

Min Heap

Let’s create a custom type, MinHeap, and then build a heap for the type.

min heap structure

After we implement all required methods for the MinHeap type, we are able to use build-in heap operations, Init, Push, Pop, Fix and Remove. You can see more details in the Golang container/heap source code.

build-in methods in container/heap

In below code implementation, we use Init and Push methods to heapify an array respectively. We also apply Pop, Fix and Remove methods on the heap data structure, you can see how the heap ordering changes from the code output.

Max Heap

The only difference from the MinHeap is the Less method as comparing two elements. We return h[i] > h[j] for max heap.

type MinHeap []int
func(h *MinHeap) Less(i, j int) bool {
     return h[i] < h[j]
}
type MaxHeap []int
func(h *MaxHeap) Less(i, j int) bool {
     return h[i] > h[j]
}

Method 2: Implement Heap Data Structure from scratch

In this session, we will build heap data structure from scratch and implement Remove, Insert, siftUp and siftDown functions.

Sift Down vs. Sift Up

• Sift down: move the value down the tree by successively exchanging the value with its smaller(for min heap)/larger(for max heap) child node.
• Sift up: move the value up the tree by successively exchanging the value with its parent node.

• Time complexity for using sift down and sift up to build a heap data structure

╔═══════════╦═════════════════╗
║           ║ Time Complexity ║
╠═══════════╬═════════════════╣
║ sift down ║ O(n)            ║ 
║ sift up   ║ O(nlogn)        ║
╚═══════════╩═════════════════╝
n: number of nodes in the tree/heap

You can check this stack overflow discussion about the time complexity in detail.

Why Sift Down is More Efficient?

Sift up operation is more expensive for the nodes lie in bottom layer to move up to the top of the tree. Likewise, sift down operation is more expensive for the nodes at the top of the tree to move down to the bottom of the tree. However, there is only one node, root node, on the top of the tree but half of nodes at the bottom of the tree. That’s the reason why sift down operation is more efficient for build heap operation.

sift down is more efficient

MinHeap

• BuildHeap: all non-leaf nodes call SiftDown to heapify the array. We starts with the last non-leaf node.
• SiftDown: continuously swap the current node with its smaller child node until it is in the correct position. (Move down)
• SiftUp: continuously swap the current node with its parent node until it is in the correct position. (Move up)
• Remove: remove the root node by swap the root node with the last node in the tree and then pop the root node which is currently at the end of tree . Call SiftDown to update heap ordering
• Insert: insert a new value at the end of the tree and call SiftUp to update heap ordering

MaxHeap

The only difference from the MinHeap is to flip the inequality as comparing two elements.

You can access the source code here.