优先队列在不同语言中的实现

Go 语言实现优先队列

Go 语言标准库没有提供优先队列的实现，但是提供了最大堆/最小堆的实现，我们可以在此基础上实现优先队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


type PriorityQueue struct {
    sort.IntSlice
}

func (pq *PriorityQueue) Less(i, j int) bool {
    // return pq.IntSlice[i] < pq.IntSlice[j] // 最小优先队列
    return pq.IntSlice[i] > pq.IntSlice[j] // 最大优先队列
}

func (pq *PriorityQueue) Push(v interface{}) {
    pq.IntSlice = append(pq.IntSlice, v.(int))
}

func (pq *PriorityQueue) Pop() interface{} {
    tmp := pq.IntSlice
    v := tmp[len(tmp)-1]
    pq.IntSlice = tmp[:len(tmp)-1]
    return v
}

注意：

入队调用的是 heap.Push 而不是调用 pq.Push，出队调用的是 heap.Pop 而不是调用 pq.Pop。
如果要构造最小堆，则 Less 函数的实现需要返回 pq.IntSlice[i] < pq.IntSlice[j]；如果要构造最大堆，则 Less 函数的实现需要返回 pq.IntSlice[i] > pq.IntSlice[j]。可以这样记忆：因为是最小堆，所以使用小于号。