2.4.22

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

解答

官方实现中已经包含了调整数组大小的代码,见:https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html
截取如下:

    // helper function to double the size of the heap array
    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }

只要在队列快满时重新分配空间,再把元素复制进去即可。
在不触发重新分配空间的情况下,
每次队列操作的比较次数上限就等于命题 Q 中给出的 $ \lg N+1 $(插入) 和 $ 2\lg N $(删除)。
插入元素最多需要 $ \lg N $ 次交换(比较次数-1),
删除元素最多需要 $1 + \lg N - 1 = \lg N$ 次交换 (注意开始时有一次交换)。
同时一次比较需要 $ 2 $ 次数组访问,一次交换需要 $4$ 次数组访问(记 a[i] 为一次数组访问)。
换算成数组访问次数就是 $ 6 \lg N + 2 $(插入)和 $ 8 \lg N $ (删除)。

在触发重新分配空间的情况下,需要额外的 $ 2N $ 次数组访问来重新分配空间。
故上限为 $ 6 \lg N +2N + 2 $ 和 $ 8 \lg N + 2N $。
如果取均摊分析,那么相当于把多出来的 $ 2N $ 次访问平均到 $ N $ 次操作中。
设第 $ n $ 次插入触发了重新分配空间,$ n $ 是 $ 2 $ 的幂。
重新分配空间进行了 $ 2 + 4 + 8 + 16 + … + 2n = 2n - 2 $ 次数组访问。
平均到 $ n $ 次插入过程,每次插入多进行 $ 2 - 2 / n $ 次数组访问。
于是插入的上限变为 $ 6 \lg N + 4 - 2 / N $。
同理删除的上限变为 $ 8 \lg N + 2 - 2 / N $。

代码

重新分配空间(C#)

/// <summary>
/// 重新调整堆的大小。
/// </summary>
/// <param name="capacity">调整后的堆大小。</param>
private void Resize(int capacity)
{
    Key[] temp = new Key[capacity];
    for (int i = 1; i <= this.n; i++)
    {
        temp[i] = this.pq[i];
    }
    this.pq = temp;
}

另请参阅

PriorityQueue 库

上一题 下一题