空堆上的容器/堆 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 示例所做的。

正如评论中所指出的，h.Pop()如果出现h.Swap()恐慌，控制将无法实现。但是，如果给定 -1 作为索引，h.Pop()仍然可以在空堆上调用：heap.Remove()

// 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()返回默认值nil是一致的，但其他程序员会发现这令人惊讶，所以我不推荐它。