2.4.13

2.4.13 #

解答 #

在官方实现的基础上直接删除 j<N 语句，随后在 DelMax() 方法中在 Sink(1) 之前让 pq[n + 1] = pq[1] 即可。

首先保存最大值，然后把堆中的第一个元素和最后一个元素交换，随后使 n = n - 1。

随后让 pq[n + 1] = pq[1]，这样在下沉操作时就不会下沉到 pq[n + 1]了。（相等的元素是不会交换的）

故之后的 Sink() 语句中不再需要进行边界判断，直接删去即可。

修改后 DelMax() 的代码如下：

public Key DelMax()
{
    if (IsEmpty())
        throw new ArgumentOutOfRangeException("Priority Queue Underflow");

    Key max = pq[1];
    Exch(1, n--);
    pq[n + 1] = pq[1];
    Sink(1);
    pq[n + 1] = default;
    if ((n > 0) && (n == pq.Length / 4))
        Resize(pq.Length / 2);

    Debug.Assert(IsMaxHeap());
    return max;
}