优先队列（小根堆）

golang实现大顶堆只看这篇文章就够了_golang 实现堆__kirakira_的博客-CSDN博客

思路

实现一个优先队列相当于维护一个小根堆，每次 pop 操作均将堆顶元素交换到堆底并返回。

Less(i, j int)如果下标 i 的元素“小于”下标 j 的元素，则返回 true，否则返回 false。返回 true 则表明 i 不会在 j 的下方。通过控制 Less 函数的返回可以实现大顶堆或者小顶堆
Push(x any)函数往IntHeap的末尾插入元素
Pop()函数取出IntHeap末尾的元素

Pop之所以这样实现，是因为在heap包的源码中，Pop在调用IntHeap的Pop之前进行了一些操作：
heap.Push函数会往堆尾插入元素，如何对这个元素进行上浮(up)操作
heap.Pop函数会先交换堆首和堆尾元素，然后再对堆首元素进行下沉(down)操作，所以我们的IntHeap类型是往堆尾插入的。

代码

package main

import (
	"container/heap"
	"fmt"
)

// MinHeap 定义一个 MinHeap 类型，用于实现 heap.Interface 接口
type MinHeap []int

// Len 实现 heap.Interface 接口中的 Len 方法
func (h MinHeap) Len() int {
	return len(h)
}

// Less 实现 heap.Interface 接口中的 Less 方法
// 从小到大排序是小根堆
// 从大到小排序是大根堆
func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

// Swap 实现 heap.Interface 接口中的 Swap 方法
func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

// Push 实现 heap.Interface 接口中的 Push 方法
func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

// Pop 实现 heap.Interface 接口中的 Pop 方法
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

// GetTop 获取堆顶元素
func (h MinHeap) GetTop() interface{} {
	if len(h) == 0 {
		return nil
	}
	return h[0]
}
func main() {
	// 定义一个大顶堆，并插入若干个元素
	h := &MinHeap{2, 1, 5, 3, 4}
	heap.Init(h)
	heap.Push(h, 8)
	// 依次从大顶堆中取出元素
	for h.Len() > 0 {
		fmt.Println(h.GetTop())
		heap.Pop(h)
	}
}

堆排序

参考：算法学习/排序/堆排序