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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

请不要在回答技术问题时复制粘贴 AI 生成的内容

这是一个创建于 616 天前的主题，其中的信息可能已经有所发展或是发生改变。

优先队列中：

需要定义 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

sharper

2024-02-06 19:17:33 +08:00 via Android

你有没有点进 heap.Push 看看实现呢？里边调用了 up 做排序

ninjashixuan

2024-02-06 19:21:06 +08:00

你这不是实现最小堆么，pop 当然是弹出最小值。less 写成 h[i] > h[j] 就是最大值了。

gostair

2024-02-06 19:21:54 +08:00

因为 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

2024-02-06 19:22:10 +08:00

堆的 Pop 是弹出队首，不要把它和栈搞混了

CLMan

2024-02-06 19:30:13 +08:00

因为`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

2024-02-06 20:14:21 +08:00 via Android

pop 首先是拷贝头部元素，然后把尾部元素移至头部并缩容，向下递归

mingyuewandao

2024-02-06 21:01:00 +08:00

@gostair 感谢大佬，豁然开朗！

cloudzhou

2024-02-07 09:58:17 +08:00

heap 我熟悉，这是我提交的 commit ，哈哈：

https://github.com/golang/go/commit/ee57e36dfa6879c05ac6717c29f2df5b546e1256

mingyuewandao

2024-02-07 14:52:18 +08:00

@cloudzhou 大佬大佬