Container/heap 空堆上的 Pop()

Question

我已经使用 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 还是希望用户始终检查是否还有剩余的物品？

Answer 1

自然的行为是恐慌。这就是 IntHeap example 的作用。

正如评论中指出的那样，如果 h.Swap() 恐慌，控制将不会到达 h.Pop()。但是，如果 heap.Remove() 给出 -1 作为索引，h.Pop() 仍然可以在空堆上调用：

// 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()
}

如果 h.Swap() 对负索引发生恐慌，h.Pop() 也应该为一致性而恐慌。

让 h.Swap() 默默地忽略负索引和 h.Pop() return 像 nil 这样的默认值是一致的，但其他程序员会发现这令人惊讶所以我不推荐一下。

Container/heap 空堆上的 Pop()

Container/heap Pop() on empty heap

heap

containers

go