Unlike Python's heapq which works directly on lists, Go's container/heap requires you to define a custom type that satisfies the heap.Interface. This abstraction offers type safety and flexibility at the cost of initial boilerplate.

The heap.Interface

To use a heap, your type (usually a slice) must implement five methods. Three come from sort.Interface, plus Push and Pop.

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

The "Magic" of Push and Pop

This is the most confusing part for beginners. You do not call your methods directly. You call heap.Push, which handles the heap invariants (sifting up/down) and calls your implementation to physically modify the slice.

1. heap.Push(h, x): Calls h.Push(x) to append, then sifts up to correct position.
2. heap.Pop(h): Swaps root with last element, sifts down new root, then calls h.Pop() to remove the last element.

Boilerplate Implementation

This is the standard pattern you will copy-paste for every heap implementation (until you use Generics).

import "container/heap"

// 1. Define the type
type IntHeap []int

// 2. Implement sort.Interface
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] } // < for MinHeap, > for MaxHeap
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

// 3. Implement Push (pointer receiver required to modify slice length)
func (h *IntHeap) Push(x any) {
    *h = append(*h, x.(int))
}

// 4. Implement Pop (pointer receiver required)
func (h *IntHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Real World Example: Merge K Sorted Lists

In this problem, we need a Min-Heap to keep track of the current smallest node among $k$ linked lists.

The Logic

1. Initialize a heap with the head of every non-empty list.
2. Pop the smallest node (the root of the heap).
3. Attach it to our result list.
4. If the popped node has a Next node, push that Next node into the heap.
5. Repeat until heap is empty.

The Code