How to Implement Heap in Go: Syntax and Example

In Go, you implement a heap by using the container/heap package which requires you to define a type that implements the heap.Interface. This interface needs methods for length, comparison, swapping, pushing, and popping elements to maintain heap properties.

Syntax

To implement a heap in Go, create a type that implements the heap.Interface. This interface requires five methods:

• Len(): returns the number of elements.
• Less(i, j int): compares elements to maintain heap order.
• Swap(i, j int): swaps elements at indexes i and j.
• Push(x interface{}): adds an element to the heap.
• Pop() interface{}: removes and returns the smallest/largest element.

Then use heap.Init, heap.Push, and heap.Pop functions to manage the heap.

go

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Example

This example shows how to create a min-heap of integers, push elements, and pop the smallest element using Go's container/heap package.

go

package main

import (
    "container/heap"
    "fmt"
)

type IntHeap []int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &IntHeap{5, 3, 8, 1}
    heap.Init(h)
    heap.Push(h, 2)
    fmt.Printf("Minimum: %d\n", (*h)[0])
    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

Output

Minimum: 1
1 2 3 5 8 

Common Pitfalls

Common mistakes when implementing a heap in Go include:

• Not using pointer receivers for Push and Pop methods, which modify the slice.
• Forgetting to call heap.Init before using the heap functions.
• Incorrectly implementing the Less method, which breaks heap order.
• Modifying the heap slice directly without using heap functions, causing invalid heap state.

go

/* Wrong: Push with value receiver (won't modify heap) */
func (h IntHeap) Push(x interface{}) {
    // *h = append(*h, x.(int)) // Error: h is not a pointer
}

/* Right: Push with pointer receiver */
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

Quick Reference

Remember these key points when working with heaps in Go:

• Implement heap.Interface with Len, Less, Swap, Push, and Pop.
• Use pointer receivers for Push and Pop to modify the heap.
• Call heap.Init before pushing or popping.
• Use heap.Push and heap.Pop to maintain heap properties.

Key Takeaways

Implement heap.Interface with Len, Less, Swap, Push, and Pop methods.

Use pointer receivers for Push and Pop to modify the heap slice correctly.

Always call heap.Init before using heap operations.

Use heap.Push and heap.Pop to maintain the heap property safely.

Ensure Less method correctly defines the heap order (min-heap or max-heap).