drze7794 2018-03-02 09:01
浏览 123
已采纳

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

In Java there is a PriorityQueue with size attribute. I'm expecting the same here (if I'm not wrong).

Use case: Read millions of data one by one and send it to a priority queue. I want only the top 5 calculated elements so I want a heap/priority queue of size 5 only.

I'm trying to use heap interface to achieve this. As to what I see golang does dynamic array increase but this is not feasible in my case.

I am referring to https://play.golang.org/p/wE413xwmxE

How can I achieve this?

  • 写回答

1条回答 默认 最新

  • douhan5547 2018-03-02 14:59
    关注

    If you just want top M smallest elements from N elements then use the heap that would give you the biggest element and prune the heap whenever its size goes over value M. Then take elements from the heap in reverse order.

    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("%v
    ", r)
    }
    

    This algorithm has memory complexity of M and time complexity of N + N * log M + M * log M.

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 数学的三元一次方程求解
  • ¥20 iqoo11 如何下载安装工程模式
  • ¥15 本题的答案是不是有问题
  • ¥15 关于#r语言#的问题:(svydesign)为什么在一个大的数据集中抽取了一个小数据集
  • ¥15 C++使用Gunplot
  • ¥15 这个电路是如何实现路灯控制器的,原理是什么,怎么求解灯亮起后熄灭的时间如图?
  • ¥15 matlab数字图像处理频率域滤波
  • ¥15 在abaqus做了二维正交切削模型,给刀具添加了超声振动条件后输出切削力为什么比普通切削增大这么多
  • ¥15 ELGamal和paillier计算效率谁快?
  • ¥15 蓝桥杯单片机第十三届第一场,整点继电器吸合,5s后断开出现了问题