在 Golang 中使用优先队列

在 Golang 中我们可以找到 heap 的实现，但是，基于 heap 的优先队列没有提供支持，只在 heap 文档中提供了优先队列的一个示例，Go 团队是在是太狗了，这对于我们这些要刷算法题，参加算法竞赛的同志们非常的不友好，而且在示例里面展示的优先队列还是 string 类型的，如果我们使用肯定是要修改的，和 C++ 相比，Go 没有 template 的特性和运算符重载的支持实在是很不方便（终于体会到什么是 “less is more"了）。

堆的实现这里就不赘述了，我们只了解以下先验知识：

• 堆是一个完全二叉树
• 堆使用数组作为底层存储，它的每个元素的子节点是2\*i，和2\*i+1
• 堆中的最小元素在下标 0 处，即完全二叉树的根
• 入队时将元素加入到数组末尾，然后进行上浮操作
• 出队时将最大值与数组末尾元素互换位置，并对根进行下沉操作

好了，我们知道这些之后，看看下面这个最简洁的优先队列例子。

type Item struct {
 value    int
 priority int
}

type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
 return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
 pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
 item := x.(*Item)
 *pq = append(*pq, item)
}

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

我们需要关注的是 Item 结构体的字段，在实际使用中可以根据需要自定义。

其次就是 Less 函数了，前面已经知道了，最小的在下标 0 处，出队时也是它，所以我们修改 Less 函数，让我们排在前面的优先级最小，这就是优先级最小的在队首优先队列，如果要得到优先级最大的在队首的优先队列只需要反转 Less 函数即可。