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. ...
2.4.14 # 解答 # 对于 n <= 2 的堆 第一步让最大元素和末端元素交换。 第二步下沉时由于 n <= 1，不需要交换。 故总共发生了一次交换，两个元素发生了交换。 对于 n = 3 的堆 第一步让最大元素和末端元素交换。 第二步如果末端元素大于另一侧的子结点，那么就不需要交换。 故最优情况时总共发生一次交换，两个元素被交换。 对于 n > 3 的堆。 第一步需要让最末端元素和最大元素交换。 由于堆中第二大的元素必定位于根节点之后。 故最末端元素一定小于该第二大元素。 因此在下沉操作时必定会和第二大元素进行交换。 故至少发生两次交换，总共有三个元素发生了交换。 构造的堆（n=15） 92 和 100 交换，随后 92 和 99 交换 构造最优情况堆的方式如下（取根结点为 100）： 对于每个结点，左子结点大于右子结点， 且左子结点的子元素都小于右子树的最小值， （上例中省略了这部分元素，可以将它们当作负数） 于是第一次 DelMax 的时候，只需要两次交换，三个元素被交换。（即 87 最后被交换到上例中 99 的位置） 第二次 DelMax 的时候，只需要三次交换，六个元素被交换. （88 交换到 97 的位置） 因此当 n > 7 时，连续两次 DelMax() 最少只需要 5 次交换。 ...
2.4.15 # 解答 # MinPQ 的官方实现见：https://algs4.cs.princeton.edu/24pq/MinPQ.java.html 事实上只需要把 MaxPQ 中的比较调换方向即可。 在线性时间内检测是否是面向最小元素的堆的方法： /// <summary> /// 确定以 k 为根节点的二叉树是不是一个最小堆。 /// </summary> /// <param name="k">需要检查的二叉树根节点。</param> /// <returns></returns> private bool IsMinHeap(int k) { if (k > this.n) return true; int left = 2 * k; int right = 2 * k + 1; if (left <= this.n && Greater(k, left)) return false; if (right <= this.n && Greater(k, right)) return false; return IsMinHeap(left) && IsMinHeap(right); } 用递归方法遍历整个二叉树，确认都满足堆的性质。由于每个结点都只会被比较三次（与父结点比较一次，与每个子结点各比较一次），由于 3N~N，因此这个方法是 O(n) 的。 ...
2.4.16 # 解答 # 最好情况比较简单，只需要一个所有键值完全相同的数组即可。 最坏情况的构造方法参考了一篇论文（见「另请参阅」部分），结果如下： 最好输入： 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 最坏输入： 1 4 7 12 10 16 14 19 17 20 5 27 8 28 2 24 9 18 6 23 11 22 21 31 13 26 25 30 15 29 3 32 ...
2.4.17 # 解答 # 英文版原文是：insert followed by remove the minimum，因此是先插入再删除。 大致上相当于一个缓冲区，把比较大的留下来，比较小的筛出去。 首先我们有一个大小为 k 的优先队列，保证最小值在最前。 接下来我们插入一个元素，可以分成两种情况。 如果插入的元素比最小值还要小，那么这个插入的元素会在之后被删除，原队列中的元素不变。 如果插入的元素比最小值大（或者相等），那么最小值会被删除，留下插入的元素。 于是可以观察到这样一个逻辑，在不断的插入过程中，比较小的元素会被过滤，只留下较大的元素。 那么我们可以把题目转化为： 向一个优先队列插入 N 个元素，保证队列的大小不超过 k，如果超过 k 了就删除最小值。 那么前 k 次插入不受影响，之后的 N-k 次插入就会按照之前说过的流程进行。 最后只留下 N 个元素中较大的 k 个元素，得证。
2.4.18 # 解答 # 首先看第一种情况，一次 insert() 接一次 delMax()。 由于插入的数比堆中的所有元素都大，这个元素会一路上升到根结点。 记上升路径上的点为 $a_1,a_2,a_3, \dots , a_k$，其中 $a_k$是插入的结点，$a_1$ 是根结点。 插入完成后路径上点的次序变为 $a_k, a_1, a_2, \dots, a_{k-1}$ 。 随后进行一次 delMax()，先做交换，次序变为 $a_{k-1}, a_1, \dots, a_{k-2}, a_k$ 。 由于 $a_1$ 是堆中原来的最大值，下沉时一定会和它交换。 根据定义，二叉堆是父结点总是优于子结点的完全二叉树，因此以后续结点作为根结点的子树也都是堆。 故同理 $a_{k-1}$ 会和 $a_2, a_3, \dots,a_{k-2}$ 交换，即沿原路径返回。 因此这种情况下前后堆不发生改变。 然后看第二种情况，操作顺序为 insert() insert() delMax() delMax()。 根据之前的结论，插入最大结点之后立即删除最大元素不会使堆发生变化，中间的两个操作抵消。 序列变为：insert() delMax()。 同理再次利用刚才的结论，操作抵消，堆不发生变化。 故第二种情况也不会使堆发生改变。
2.4.19 # 解答 # 官方实现已经包含了这部分的代码，见：https://algs4.cs.princeton.edu/24pq/MaxPQ.java.html 相应的构造函数（Java） public MaxPQ(Key[] keys) { n = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i < n; i++) pq[i+1] = keys[i]; for (int k = n/2; k >= 1; k--) sink(k); assert isMaxHeap(); } 代码 # 构造函数（C#） /// <summary> /// 从已有元素建立一个最大堆。（O(n)） /// </summary> /// <param name="keys">已有元素。</param> public MaxPQ(Key[] keys) { _n = keys.Length; pq = new Key[keys.Length + 1]; for (var i = 0; i < keys. ...
2.4.20 # 解答 # 官网给出了解答：https://algs4.cs.princeton.edu/24pq/ 首先介绍第一种解法。 设叶子结点的高度为 $0$，根结点的高度为 $ h $。 于是某个结点 sink 时的最大交换次数即为该结点的高度。 故某一层结点的最大交换次数为 该层结点数 × 该层的高度。 于是总交换次数最大为： $$ \begin{align*} & h+2(h-1)+2^2(h-2)+ \dots + 2^h(0) \newline & =\sum_{k=0}^{h-1} 2^k(h-k) \newline & =h\sum_{k=0}^{h-1}2^k - \sum_{k=0}^{h-1}k2^k \newline \end {align*} $$ 第一项为等比数列的和，第二项为等差数列乘以等比数列的和。 于是第一项可以直接通过公式求得，第二项可以利用错位相减法求得。 $$ \begin{align} & h\sum_{k=0}^{h-1}2^k - \sum_{k=0}^{h-1}k2^k \newline & =h2^{h}-h-\sum_{k=0}^{h-1}k2^k \newline & =h2^{h}-h +\sum_{k=0}^{h-1} k2^k - 2\sum_{k=0}^{h-1} k2^k \newline & =h2^{h}-h+2^h - 2-(h-1)2^h \newline & =2^{h+1}-h-2 \newline & =N-h-1 \le N \end{align} $$ ...
2.4.21 # 解答 # 给元素添上序号组成结点，按照序号排序即可，每个结点可以用类似于这样的实现： class ElemType<T> : IComparable<ElemType<T>> { private int _key; private T _element; public ElemType(int key) => _key = key; public int CompareTo(ElemType<T> other) { return _key.CompareTo(other._key); } } 栈： 用最大元素在最前的优先队列。 每个结点都包含一个元素和一个序号， 插入新元素时序号递增，这样最后插入的元素总在最前。 队列： 用最小元素在最前的优先队列。 每个结点都包含一个元素和一个序号， 插入新元素时序号递增，这样最先插入的元素总在最前。 随机队列： 优先队列的选择任意 每个结点都包含一个元素和一个序号， 插入新元素时随机指定一个序号，这样元素的顺序就是任意的了。
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$ 次交换 （注意开始时有一次交换）。 ...