container包定义了一套heap的接口，只要实现了这些接口就能作为一个heap来使用,定义如下

go
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// heap 包为任何实现 heap.Interface 接口的类型提供堆操作。堆是一种具有以下特性的树形结构，
// 即每个节点都是其子树中值最小的节点。
//
// 树中的最小元素是根，索引为 0。
//
// 堆通常用于实现优先队列。要构建优先队列，请使用 (负) 优先级作为 Less 方法的排序，
// 这样 Push 就会添加项目，而 Pop 就会从队列中删除优先级最高的项目。
// 示例包括了这样一个实现；文件 example_pq_test.go 包含了完整的源代码。



package heap

import "sort"

// Interface 类型描述了使用此包中的例程的类型的要求。
// 任何实现此接口的类型都可用作最小堆，具有以下不变性（在调用 Init 后或数据为空或排序后）：
//
//	!h.Less(j, i) 对于 0 <= i < h.Len() 且 2*i+1 <= j <= 2*i+2 且 j < h.Len() 均成立
//
// 注意，此接口中的 Push 和 Pop 是供此包的实现调用的。
// 若要从堆中添加和删除元素，请使用 heap.Push 和 heap.Pop。

type Interface interface {
	sort.Interface
	Push(x any) // 将 x 添加为元素 Len()
	Pop() any   // 移除并返回元素 Len() - 1。
}

// Init 根据此包中的其他例程所需的堆不变性建立堆。
// 对于堆不变性来说，Init 是幂等的，可能在堆不变性可能无效时调用。
// 复杂度为 O(n)，其中 n = h.Len()。
func Init(h Interface) {
	// heapify
	n := h.Len()
	for i := n/2 - 1; i >= 0; i-- {
		down(h, i, n)
	}
}

// Push 将元素 x 推入堆中。
// 复杂度为 O(log n)，其中 n = h.Len()。
func Push(h Interface, x any) {
	h.Push(x)
	up(h, h.Len()-1)
}

// Pop 从堆中移除并返回最小元素（根据 Less）。
// 复杂度为 O(log n)，其中 n = h.Len()。
// Pop 等效于 Remove(h, 0)。
func Pop(h Interface) any {
	n := h.Len() - 1
	h.Swap(0, n)
	down(h, 0, n)
	return h.Pop()
}

// Remove 从堆中移除并返回索引 i 的元素。
// 复杂度为 O(log n)，其中 n = h.Len()。
func Remove(h Interface, i int) any {
	n := h.Len() - 1
	if n != i {
		h.Swap(i, n)
		if !down(h, i, n) {
			up(h, i)
		}
	}
	return h.Pop()
}

// Fix 在索引 i 的元素更改其值后重新建立堆顺序。
// 更改元素在索引 i 的值，然后调用 Fix 相当于调用 Remove(h, i)，
// 然后将新值推入堆中。复杂度为 O(log n)，其中 n = h.Len()。
func Fix(h Interface, i int) {
	if !down(h, i, h.Len()) {
		up(h, i)
	}
}

// up 将索引 j 处的元素向堆的根移动，直到满足堆不变性。
func up(h Interface, j int) {
	for {
		i := (j - 1) / 2 // 父节点
		if i == j || !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		j = i
	}
}

// down 将索引 i0 处的元素向堆的叶子移动，直到满足堆不变性。
// 如果 i0 已经是叶子，则返回 false。
func down(h Interface, i0, n int) bool {
	i := i0
	for {
		j1 := 2*i + 1
		if j1 >= n || j1 < 0 { // 在 int 溢出后 j1 < 0
			break
		}
		j := j1 // 左孩子
		if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
			j = j2 // = 2*i + 2  // 右孩子
		}
		if !h.Less(j, i) {
			break
		}
		h.Swap(i, j)
		i = j
	}
	return i > i0
}

使用实例

go
package main

import (
	"container/heap"
	"fmt"
)

// 为整数切片实现 heap.Interface 接口
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] }

// Push 将元素推入堆中
func (h *IntHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 从堆中弹出最小元素
func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main() {
	// 初始化一个空堆
	var h IntHeap
	heap.Init(&h)

	// 将元素推入堆中
	heap.Push(&h, 3)
	heap.Push(&h, 5)
	heap.Push(&h, 1)

	// 从堆中弹出并打印最小元素
	fmt.Printf("Minimum: %d\n", heap.Pop(&h))

	// 将元素推入堆中
	heap.Push(&h, 4)

	// 打印堆中的所有元素
	for h.Len() > 0 {
		fmt.Printf("%d ", heap.Pop(&h))
	}
}