17370845950

Go标准库container/heap不直接提供最小堆或最大堆类型，而是通过实现heap.Interface接口（含Len、Less、Swap及Push、Pop方法）配合heap函数使用；最小堆由Less返回a[i]a[j]；泛型封装可复用逻辑，支持任意类型和序关系；使用时需传指针、调用Init建堆、注意Pop行为。

Go 语言标准库 container/heap 并不直接提供最小堆或最大堆类型，而是提供一个通用的堆操作接口，需要你实现 heap.Interface（即 sort.Interface + 两个方法），再配合 heap.Init、heap.Push、heap.Pop 等函数使用。关键在于：最小堆和最大堆的区别，只取决于你如何定义 Less(i, j int) bool 方法。

最小堆：按元素值升序排列（小根堆）

要让堆顶始终是最小元素，只需在 Less 中返回 a[i] 。下面是一个基于整数切片的最小堆示例：

// 定义最小堆类型（包装 []int）

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] } // 关键：小的在前
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

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

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

// 使用示例

h := &MinHeap{}
heap.Init(h)

heap.Push(h, 5)
heap.Push(h, 2)
heap.Push(h, 8)
heap.Push(h, 1)

fmt.Println(heap.Pop(h)) // 1
fmt.Println(heap.Pop(h)) // 2
fmt.Println(heap.Pop(h)) // 5

最大堆：按元素值降序排列（大根堆）

只需把 Less 的逻辑反过来：返回 a[i] > a[j]，其余代码完全一致：

// 定义最大堆类型

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] } // 关键：大的在前（即 i 更“小”当 h[i] 更大）
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

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

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

// 使用示例

h := &MaxHeap{}
heap.Init(h)

heap.Push(h, 5)
heap.Push(h, 2)
heap.Push(h, 8)
heap.Push(h, 1)

fmt.Println(heap.Pop(h)) // 8
fmt.Println(heap.Pop(h)) // 5
fmt.Println(heap.Pop(h)) // 2

泛型方式（Go 1.18+）：复用逻辑，避免重复定义

若需支持多种类型（如 float64、自定义结构体），可借助泛型封装通用堆结构。注意：标准库 container/heap 本身不支持泛型，但你可以自己写一个泛型 wrapper：

• 定义一个泛型类型 Heap[T any]，内部持有 []T 和比较函数 less func(a, b T) bool
• 实现 Len/Less/Swap/Push/Pop，其中 Less 调用传入的 less 函数
• 初始化时传入具体比较逻辑：less: func(a, b int) bool { return a → 最小堆；a > b → 最大堆

这样一份实现即可支持任意可比较类型和任意序关系，无需为每种类型/方向重复写四五个方法。

常见注意事项

• 必须用指针调用 heap 方法：例如 heap.Push(&h, x)，因为 Push/Pop 会修改底层切片（可能触发扩容）
• 初始化不能省略：即使切片非空，也必须先调用 heap.Init(&h) 建堆，否则结构不满足堆序
• Pop 返回的是堆顶，不是最后一个元素：它会自动重排剩余元素，保持堆性质
• 不支持随机访问或查找：heap 不是搜索结构，仅保证堆顶极值，其他位置无序