V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
mingyuewandao
V2EX  ›  程序员

关于 go 的优先队列问题,这里大佬多,帮忙看看

  •  
  •   mingyuewandao · 289 天前 · 1643 次点击
    这是一个创建于 289 天前的主题,其中的信息可能已经有所发展或是发生改变。

    优先队列中:

    需要定义 Pop()函数,Pop 函数定义的时候,明明是把队尾的元素(列表是从小到大排序,队尾即为最大值)删除,但是效果却是把队首(最小值)删除?

    源码位置:

    https://github.com/golang/go/blob/6076edc55c548878c261316f3e3294f1f73125a3/src/container/heap/example_intheap_test.go#L26

    看这里明明是把队列的尾元素去除

    func (h *IntHeap) Pop() any {
    	old := *h
    	n := len(old)
    	x := old[n-1]
    	*h = old[0 : n-1]
    	return x
    }
    

    打印的效果:

    Pop 的时候竟然是最小的先出来??

    // This example inserts several ints into an IntHeap, checks the minimum,
    // and removes them in order of priority.
    func Example_intHeap() {
    	h := &IntHeap{2, 1, 5}
    	heap.Init(h)
    	heap.Push(h, 3)
    	fmt.Printf("minimum: %d\n", (*h)[0])
    	for h.Len() > 0 {
    		fmt.Printf("%d ", heap.Pop(h))
    	}
    	// Output:
    	// minimum: 1
    	// 1 2 3 5
    }
    
    9 条回复    2024-02-07 14:52:18 +08:00
    starck
        1
    starck  
       289 天前 via Android
    你有没有点进 heap.Push 看看实现呢?里边调用了 up 做排序
    ninjashixuan
        2
    ninjashixuan  
       289 天前
    你这不是实现最小堆么,pop 当然是弹出最小值。less 写成 h[i] > h[j] 就是最大值了。
    gostair
        3
    gostair  
       289 天前
    因为 Example_intHeap,的最后一行.
    fmt.Printf("%d ", heap.Pop(h)),调用的是"container/heap"包下的 heap.pop 方法,其实现为:


    ```
    // Pop 从堆中移除并返回最小元素
    //Pop 相当于 Remove ( h ,0 )。
    func Pop(h Interface) any {
    n := h.Len() - 1
    // 注意看这里
    h.Swap(0, n)
    down(h, 0, n)
    return h.Pop()
    }


    ```

    而 Swap 的方法实现是:
    ```
    // 很明显就是将索引元素交换
    func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
    ```

    综上 IntHeap.Swap(0,n),也就是将队首和对位交换了.
    pastor
        4
    pastor  
       289 天前
    堆的 Pop 是弹出队首,不要把它和栈搞混了
    CLMan
        5
    CLMan  
       289 天前
    因为`func (h *IntHeap) Pop()`是 golang 的 heap 的实现细节:

    type Interface interface {
    sort.Interface
    Push(x any) // add x as element Len()
    Pop() any // remove and return element Len() - 1.
    }

    而真正堆的 pop 方法是`heap.Pop()`函数,别把两者弄混了。
    Nazz
        6
    Nazz  
       289 天前 via Android
    pop 首先是拷贝头部元素,然后把尾部元素移至头部并缩容,向下递归
    mingyuewandao
        7
    mingyuewandao  
    OP
       289 天前
    @gostair 感谢大佬 ,豁然开朗!
    cloudzhou
        8
    cloudzhou  
       288 天前
    heap 我熟悉,这是我提交的 commit ,哈哈:

    https://github.com/golang/go/commit/ee57e36dfa6879c05ac6717c29f2df5b546e1256
    mingyuewandao
        9
    mingyuewandao  
    OP
       288 天前
    @cloudzhou 大佬大佬
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1347 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 23:49 · PVG 07:49 · LAX 15:49 · JFK 18:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.