2.4.22 #
解答 #
官方实现中已经包含了调整数组大小的代码，见：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 (var i = 1; i <= _n; i++)
{
temp[i] = _pq[i];
}
_pq = temp;
}