The heap data structure is commonly used to implement a priority queue. The are many heap variants, but in this blog post we’ll focus on the binary heap. Our implemention will specifically be a min heap, and it’ll only work for integer values.

Side note: we’ll be able to adapt this to work for any value when Golang officially releases generics!

Definitions⌗

Binary Heap

A complete binary tree that adheres to the heap property.

Complete Binary Tree

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Heap Property

The key stored in each node is either greater than or equal to or less than or equal to the keys in the node’s children Here’s what the my BinaryHeap data structure looks like

Wikipedia

Struct Definition⌗

type BinaryHeap struct {
    heap []int
}

This is our binary heap struct definition. We have only one field, the heap int slice. A binary heap can be implicitly represented using a slice. Each key’s index represents its position in the tree, and we can easily calculate the child-parent relationships.

Children Indices⌗

Left Child  = 2 * i + 1
Right Child = 2 * i + 2

Parent Index⌗

Parent = (i - 1) / 2

Implementing The Push Method⌗

New keys are pushed to the end of the binary heap. The key needs to be “bubbled up” to its valid position. We examine its parent, and determine if the key we added is less than the parent.

If it is, we swap the key with its parent. We repeat this until we’ve reached the root index (i.e. 0) or the key is greater than the parent.

func (bh *BinaryHeap) Push(key int) {
    bh.heap = append(bh.heap, key)
    bh.bubbleUp(len(bh.heap)-1)
}

func (bh *BinaryHeap) bubbleUp(index int) {
    for index > 0 {
        parentIndex := (index - 1) / 2

        if bh.heap[parentIndex] < bh.heap[index] {
            return
        }

        bh.heap[parentIndex], bh.heap[index] = bh.heap[index], bh.heap[parentIndex]
        index = parentIndex
    }
}

Implementing the Pop method⌗

We must temporarily store the root key before we pop from the binary heap. First, we replace the root key with the key in the last position. Second, we “bubble down” the key to its valid position. We need to determine whether we take the left or right path when bubbling down. We choose the path with the child holding the minimum key.

For example, we are at some key with a left child key 5 and a right child key 7. We choose the left child because 5 is less than 7.

After getting the minimun child key, we compare it to the current key. If the current key is greater than the child, we swap. We continue this process until the current key has no children or the key is less than the child (i.e. the correct position).

Finally, we return the original root value stored in a temporary variable.

func (bh *BinaryHeap) Pop() int {
    popped := bh.heap[0]
    heapSize := len(bh.heap)

    if heapSize > 1 {
        bh.heap[0] = bh.heap[len(bh.heap)-1]
    }

    bh.heap = bh.heap[:len(bh.heap)-1]
    bh.bubbleDown(0)
    return popped
}

func (bh *BinaryHeap) bubbleDown(index int) {
    for 2*index + 1 < len(bh.heap) {
        minChildIndex := bh.minChildIndex(index)

        if bh.heap[minChildIndex] > bh.heap[index] {
            return
        }

        bh.heap[minChildIndex], bh.heap[index] = bh.heap[index], bh.heap[minChildIndex]
        index = minChildIndex
    }
}

func (bh *BinaryHeap) minChildIndex(index int) int {
    if 2*index + 2 >= len(bh.heap) {
        return 2*index + 1
    }

    if bh.heap[2*index + 2] < bh.heap[2*index + 1] {
        return 2*index + 2
    }

    return 2*index + 1
}

Conclusion⌗

Implementing a binary heap in Golang is simple, and can be used to solve any problem that requires a priority queue.

I encourage you to adapt this implementation for another data type.

Thanks for reading! Let me know what you think of this post on Twitter.