2.4.13

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

在官方实现的基础上直接删除 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 = this.pq[1];
    Exch(1, this.n--);
    pq[n + 1] = pq[1];
    Sink(1);
    this.pq[this.n + 1] = default(Key);
    if ((this.n > 0) && (this.n == this.pq.Length / 4))
        Resize(this.pq.Length / 2);

    Debug.Assert(IsMaxHeap());
    return max;
}
上一题 下一题