英文:
Container/heap Pop() on empty heap
问题
我使用了container/heap包来实现一个优先队列。但有一件事让我困扰。如果堆为空，interface.Pop()方法应该如何行为？我在文档中没有看到任何提及，源代码似乎也没有考虑这种情况：
// Pop removes the minimum element (according to Less) from the heap
// and returns it. The complexity is O(log(n)) where n = h.Len().
// It is equivalent to Remove(h, 0).
//
func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}
显然，如果h.Len()为0，这个方法将无法正常工作。这是简单地引发panic，还是用户需要始终检查是否还有剩余的项？
英文:
I have used the container/heap package to implement a priority queue. One thing bothers me though. What should the behaviour of the interface.Pop() method be if the heap is empty? I don't see anything mentioned in the documentation and the source code doesn't seem to be expecting this situation:
// Pop removes the minimum element (according to Less) from the heap
// and returns it. The complexity is O(log(n)) where n = h.Len().
// It is equivalent to Remove(h, 0).
//
func Pop(h Interface) interface{} {
n := h.Len() - 1
h.Swap(0, n)
down(h, 0, n)
return h.Pop()
}
Clearly, if h.Len() is 0 this is not going to work well. Is this simply meant to panic or is the user expected to always check whether there are any items left?
答案1
得分: 1
自然的行为是恐慌。这就是IntHeap示例的做法。
正如评论中指出的，如果h.Swap()引发恐慌，控制流将不会到达h.Pop()。然而，如果heap.Remove()给定-1作为索引，仍然可以在空堆上调用h.Pop()：
// Remove从堆中删除索引为i的元素。
// 复杂度为O(log(n))，其中n = h.Len()。
//
func Remove(h Interface, i int) interface{} {
n := h.Len() - 1
if n != i {
h.Swap(i, n)
down(h, i, n)
up(h, i)
}
return h.Pop()
}
如果h.Swap()在负索引上引发恐慌，为了保持一致性，h.Pop()也应该引发恐慌。
让h.Swap()静默地忽略负索引并使h.Pop()返回一个默认值，如nil，是一致的，但其他程序员可能会觉得这令人惊讶，所以我不建议这样做。
英文:
The natural behaviour is to panic. This is what the IntHeap example does.
As pointed out in the comments, control will not reach h.Pop() if h.Swap() panics. However, h.Pop() can still be called on an empty heap if heap.Remove() is given -1 as the index:
// Remove removes the element at index i from the heap.
// The complexity is O(log(n)) where n = h.Len().
//
func Remove(h Interface, i int) interface{} {
n := h.Len() - 1
if n != i {
h.Swap(i, n)
down(h, i, n)
up(h, i)
}
return h.Pop()
}
If h.Swap() panics on negative indices, h.Pop() should also panic for consistency.
Having h.Swap() silently ignore negative indices and h.Pop() return a default value like nil is consistent, but other programmers would find that surprising so I don't recommend it.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论