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} $$

于是交换次数小于 $N$，比较次数小于 $2N$。

另一种解法，可以配合官网的图片帮助理解。

首先堆中某个结点最多一路下沉到叶子结点，

最大交换次数就是该结点的高度（记叶子结点的高度为 0）。

考虑根结点一路下沉到叶子结点的轨迹，

设为 $a_0, a_1, a_2, … , a_k$，其中 $k$ 为根结点的高度，$a_0$ 是根结点。

$a_0$ 下沉后结点顺序变为 $a_1, a_2, …, a_k, a_0$ 。

根据下沉的定义，有 $a_1 > a_2 > \dots > a_k > a_0$ 。

因此 $a_1$ 下沉时不可能与 $a_2$ 交换，而会向另一个方向下沉。

其余结点同理，可以发现每个结点的下沉路径不会与其他结点重合。

一棵完全二叉树共有 $N - 1$ 条边，每访问一条边代表进行了一次交换。

故交换次数必定小于 $N$，比较次数为交换次数的两倍小于 $2N$。