container/heap

container/heap Init, Push, and Pop, including the requirement that interface Push and Pop operate at the tail and that callers must use heap.Push and heap.Pop, checked on Go 1.24.0.

模块页正文目前为英文。

The container/heap package provides heap operations for any type that implements heap.Interface. A heap is a tree in which each node is less than or equal to its children according to Less, so the minimum is at index 0. This page does not rewrite package sort, even though Interface embeds sort.Interface.

Official documentation states that the Push and Pop methods on the interface are for package heap to call: Push must add x as element Len(), and Pop must remove and return element Len()-1, that is, the tail of the slice. To add or remove items from the heap, call heap.Push and heap.Pop, which restore the invariants. Calling the methods directly only appends or pops the tail and can break the heap, as the second example shows.

A heap is a common way to implement a priority queue. This page does not promise any particular order among items that compare equal. Equal priorities are not a FIFO or stable sequence unless your own Less function defines one, and container/heap does not add that guarantee. Examples use unique integer priorities so the output is deterministic.

Examples were checked against Go 1.24.0. See the official package documentation for the complete API.

Go reference overview →

API index

APISummary
heap.Init, heap.Push, and heap.PopImplement Push and Pop at the tail. Call heap.Push and heap.Pop to maintain the heap. Calling the methods directly can violate the invariants.

Interface, Init, Push, and Pop

Implement Len, Less, and Swap from sort.Interface, plus Push and Pop that operate on the last index. heap.Init establishes the invariants in O(n). heap.Push and heap.Pop then run in O(log n).

The first program inits a three-element heap, pushes 1 with heap.Push, and pops 1, 3, 4, 5. The second program calls the slice method Push directly after Init. That appends 1 at the tail without sifting it up, and heap.Pop then returns 3 first, not 1. That is why the package methods, not the interface methods alone, must be used after the heap is in use.

heap.Init, heap.Push, and heap.Pop

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

Implement Push and Pop at the tail. Call heap.Push and heap.Pop to maintain the heap. Calling the methods directly can violate the invariants.

ParameterDescription
hA pointer to a type that implements heap.Interface. Examples use *intHeap so Push and Pop can resize the slice.
xThe element passed to heap.Push. The interface Push method should append it as the new last element.

Returns: heap.Pop returns the minimum element according to Less, after restoring the heap. The broken path in this example is only to show a violated invariant; it is not a usage pattern.

  • The first line is the correct sequence: 1 3 4 5. The second line starts with 3 because 1 was appended without heap.Push.
  • Equal priorities are not demonstrated here, and no pop order is promised for items that Less treats as equal.
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 any)        { *h = append(*h, x.(int)) }
func (h *intHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func main() {
	h := intHeap{5, 3, 4}
	heap.Init(&h)
	heap.Push(&h, 1)
	fmt.Println(heap.Pop(&h), heap.Pop(&h), heap.Pop(&h), heap.Pop(&h))

	broken := intHeap{5, 3, 4}
	heap.Init(&broken)
	broken.Push(1) // appends at the tail without restoring the heap
	fmt.Println(heap.Pop(&broken), heap.Pop(&broken), heap.Pop(&broken), heap.Pop(&broken))
}

Expected output

1 3 4 5
3 1 4 5

Related: sort.Interface, cmp.Less, Official container/heap

Official documentation →