# Max Heap in Go

tech · Jan 16, 2021 · ~8 min

Same as the case here, I just wanted to revisit another data structure. Well, Max Heap (also Min Heap) is a data structure that commonly used to create a priority queue which also a complete binary tree that has nodes which value is greater (or lesser) than its children value.

Not like BST that I implemented before, Max Heap commonly implemented using array in order to make it easier (I think) to access its children. To accessing each nodes parent or children you can visualize the whole array as a tree. I have no image for it, so I pick Max Heap image from another website. The concept is the same with Min Heap tho.

Finally we start array from 1 (LOL). Why we start from 1? Because index 0 couldn’t be accessed by this formula.

Refer to the provided image above, we can visualize that left child of a node is on the `currentIndex * 2`, the right child is on the `currentIndex * 2 + 1`, and you can access the parent of the node by using `currentIndex / 2`.

For example, Node with value `15`, has 2 children which are `10` and `5`. You can see the index of `15` which is `3`. Its left child is `10` which has index `3 * 2 = 6`, and its right children is `5` which has index `3 * 2 + 1 = 7`.

Enough with the theory, you can read it from your book. I only want to write the implementation here using Go. I only implement `Push`, `Pop`, and `Peek` operation. It’s hard to decide the name of the operation, but as long as it describes the operation please don’t mind.

## Define MaxHeap Struct

 ``````1 2 3 4 5 6 `````` ``````type MaxHeap struct { heap []int capacity int size int root int } ``````

MaxHeap will have at least size, capacity, and heap itself. `root` attribute will be `constant` since its root should always be `1`. `size` will define the current size of the heap, `capacity` will define how much the heap can store data, and the `heap` itself is an array that we stored the data into.

## Constructor

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````func NewMaxHeap(capacity int) *MaxHeap { // because we used the 0 index // we need to increase the capacity defined by user c := capacity + 1 h := make([]int, c, c) // just to mark that it is the minimum one, // you can ignore this h[0] = (1 << 31) - 1 return &MaxHeap{ root: 1, // always 1, you can omit this attribute size: 0, capacity: c, heap: h, } } ``````

## Helper Method

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 `````` ``````func (MaxHeap) getParent(idx int) int { return idx / 2 } func (MaxHeap) getLeft(idx int) int { return idx * 2 } func (MaxHeap) getRight(idx int) int { return idx*2 + 1 } func (m *MaxHeap) swap(idx1, idx2 int) { m.heap[idx1], m.heap[idx2] = m.heap[idx2], m.heap[idx1] } func (m MaxHeap) String() string { return fmt.Sprintf(`size: %v capacity: %v heap: %v`, m.size, m.capacity-1, m.heap[1:]) } ``````

## Push

Push into max / min heap should be easy, just put the element where it belongs according to the index, and check if its value is greater / lesser than its parent, if you’re implementing max heap, check whether its value is greater than its parent, if so swap its value with its parent value.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 `````` ``````func (m *MaxHeap) Push(element int) { // check whether it can store the element if m.size >= m.capacity-1 { return } m.size++ idx := m.size // put it according to the index m.heap[idx] = element parent := m.getParent(idx) // check if its value is greater than its parent for m.heap[idx] > m.heap[parent] { // then swap m.swap(idx, parent) // repeat the process until // the greatest value is on the top idx = parent parent = m.getParent(idx) } } ``````

## Peek

Peek operation will return the greatest / least value which is the root.

 ``````1 2 3 4 5 6 7 `````` ``````func (m MaxHeap) Peek() (int, error) { if m.size <= 0 { return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty") } return m.heap[m.root], nil } ``````

Let’s check our heap

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````func main() { h := NewMaxHeap(15) h.Push(1) h.Push(4) h.Push(2) h.Push(5) fmt.Println(h) g, _ := h.Peek() fmt.Println("greatest:", g) } ``````

The output should be like this:

 ``````1 2 3 4 `````` ``````size: 4 capacity: 15 heap: [5 4 2 1 0 0 0 0 0 0 0 0 0 0 0] greatest: 5 ``````

## Pop

Now let’s pop something. Popping operation will return value of the greatest / least value and delete it from the heap. We need to rebalance the heap So the greatest / least value will be the root again.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 `````` ``````func (m *MaxHeap) rebalance(idx int) { // don't rebalance if node index // is greater than heap size if idx >= m.size { return } // fetch the left child index left := m.getLeft(idx) // fetch the right child index right := m.getRight(idx) // only swap if children position is wrong // and only the children index is less than heap size // and then rebalance it if left <= m.size { if m.heap[idx] < m.heap[left] { m.swap(idx, left) m.rebalance(left) } } if right <= m.size { if m.heap[idx] < m.heap[right] { m.swap(idx, right) m.rebalance(right) } } } func (m *MaxHeap) Pop() (int, error) { if m.size <= 0 { return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty") } // fetch the root max := m.heap[m.root] // make the route is the last element in the heap m.heap[m.root] = m.heap[m.size] // make it zero value m.heap[m.size] = 0 // decrease the size so the zero value won't be counted m.size-- // rebalance the heap m.rebalance(m.root) // return the greatest return max, nil } ``````

So whenever Pop operation is called, the heap will rebalance it from the top until its leaf. The whole code should be look like this:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 `````` ``````package main import "fmt" type MaxHeap struct { heap []int capacity int size int root int } func (MaxHeap) getParent(idx int) int { return idx / 2 } func (MaxHeap) getLeft(idx int) int { return idx * 2 } func (MaxHeap) getRight(idx int) int { return idx*2 + 1 } func (m *MaxHeap) swap(idx1, idx2 int) { m.heap[idx1], m.heap[idx2] = m.heap[idx2], m.heap[idx1] } func (m MaxHeap) String() string { return fmt.Sprintf(`size: %v capacity: %v heap: %v`, m.size, m.capacity-1, m.heap[1:]) } func (m *MaxHeap) rebalance(idx int) { if idx >= m.size { return } left := m.getLeft(idx) right := m.getRight(idx) if left <= m.size { if m.heap[idx] < m.heap[left] { m.swap(idx, left) m.rebalance(left) } } if right <= m.size { if m.heap[idx] < m.heap[right] { m.swap(idx, right) m.rebalance(right) } } } func (m *MaxHeap) Pop() (int, error) { if m.size <= 0 { return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty") } // fetch the root max := m.heap[m.root] // make the route is the last element in the heap m.heap[m.root] = m.heap[m.size] // make it zero value m.heap[m.size] = 0 // decrease the size so the zero value won't be counted m.size-- // rebalance the heap m.rebalance(m.root) // return the greatest return max, nil } func (m MaxHeap) Peek() (int, error) { if m.size <= 0 { return (1 << 31) - 1, fmt.Errorf("max-heap: heap is empty") } return m.heap[m.root], nil } func (m *MaxHeap) Push(element int) { // exceed the limit if m.size >= m.capacity-1 { return } m.size++ idx := m.size m.heap[idx] = element parent := m.getParent(idx) for m.heap[idx] > m.heap[parent] { m.swap(idx, parent) idx = parent parent = m.getParent(idx) } } func NewMaxHeap(capacity int) *MaxHeap { // because we used the 0 index // we need to increase the capacity defined by user c := capacity + 1 h := make([]int, c, c) // just to mark that it is the minimum one, // you can ignore this h[0] = (1 << 31) - 1 return &MaxHeap{ root: 1, // always 1, you can omit this attribute size: 0, capacity: c, heap: h, } } func main() { h := NewMaxHeap(15) h.Push(1) h.Push(4) h.Push(2) h.Push(5) h.Push(3) h.Push(10) fmt.Println(h.Pop()) fmt.Println(h.Pop()) fmt.Println(h.Pop()) h.Push(11) fmt.Println(h) } ``````

Thank you for reading!

· · ·

## Love This Content?

Any kind of supports is greatly appreciated! Kindly support me via Bitcoin, Ko-fi, Trakteer, or just continue to read another content. You can write a response via Webmention and let me know the URL via Telegraph.