限制 Go 堆接口实现的优先级队列的大小

Question

在Java中，有一个带有size属性的PriorityQueue。我在这里期待同样的事情(如果我没错的话(。

用例：逐个读取数百万个数据，并将其发送到优先级队列。我只想要前 5 个计算元素，所以我只想要大小为 5 的堆/优先级队列。

我正在尝试使用堆接口来实现这一点。至于我所看到的golang确实增加了动态阵列，但这在我的情况下是不可行的。

我指的是 https://play.golang.org/p/wE413xwmxE

我怎样才能做到这一点？

Answer 1

如果您只想要 N 个元素中的前 M 个最小元素，请使用将为您提供最大元素的堆，并在堆大小超过值 M 时修剪堆。然后以相反的顺序从堆中获取元素。

package main
import (
    "container/heap"
    "fmt"
    "math/rand"
)
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] }
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}
const (
    n = 1000000
    m = 5
)
func main() {
    h := &IntHeap{}
    heap.Init(h)
    for i := 0; i < n; i++ {
        x := rand.Intn(n)
        heap.Push(h,x)
        if h.Len() > m {
            heap.Pop(h)
        }
    }
    r := make([]int, h.Len())
    for i := len(r) - 1; i >= 0; i-- {
        r[i] = heap.Pop(h).(int)
    }
    fmt.Printf("%vn", r)
}

该算法的内存复杂度为 M，时间复杂度为 N + N * log M + M * log M。