优先队列中:
需要定义 Pop()函数,Pop 函数定义的时候,明明是把队尾的元素(列表是从小到大排序,队尾即为最大值)删除,但是效果却是把队首(最小值)删除?
源码位置:
看这里明明是把队列的尾元素去除
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
}
1
starck 272 天前 via Android
你有没有点进 heap.Push 看看实现呢?里边调用了 up 做排序
|
2
ninjashixuan 272 天前
你这不是实现最小堆么,pop 当然是弹出最小值。less 写成 h[i] > h[j] 就是最大值了。
|
3
gostair 272 天前
因为 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),也就是将队首和对位交换了. |
4
pastor 272 天前
堆的 Pop 是弹出队首,不要把它和栈搞混了
|
5
CLMan 272 天前
因为`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()`函数,别把两者弄混了。 |
6
Nazz 272 天前 via Android
pop 首先是拷贝头部元素,然后把尾部元素移至头部并缩容,向下递归
|
7
mingyuewandao OP @gostair 感谢大佬 ,豁然开朗!
|
8
cloudzhou 272 天前
heap 我熟悉,这是我提交的 commit ,哈哈:
https://github.com/golang/go/commit/ee57e36dfa6879c05ac6717c29f2df5b546e1256 |
9
mingyuewandao OP @cloudzhou 大佬大佬
|