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

V2EX = way to explore

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

现在注册

已注册用户请登录

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

优先队列中：

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

298 天前 via Android

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

ninjashixuan

298 天前

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

gostair

298 天前

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

298 天前

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

CLMan

298 天前

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

298 天前 via Android

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

mingyuewandao

298 天前

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

cloudzhou

298 天前

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

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

mingyuewandao

298 天前

@cloudzhou 大佬大佬