2.4.20

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

解答

官网给出了解答:https://algs4.cs.princeton.edu/24pq/

首先介绍第一种解法。
设叶子结点的高度为 $ 0 $,根结点的高度为 $ h ​$。
于是某个结点 sink 时的最大交换次数即为该结点的高度。
故某一层结点的最大交换次数为 该层结点数 × 该层的高度。
于是总交换次数最大为:
$$
\begin{align*}
& h+2(h-1)+2^2(h-2)+ \dots + 2^h(0) \\
& =\sum_{k=0}^{h-1} 2^k(h-k) \\
& =h\sum_{k=0}^{h-1}2^k - \sum_{k=0}^{h-1}k2^k \\
\end {align*}
$$
第一项为等比数列的和,第二项为等差数列乘以等比数列的和。
于是第一项可以直接通过公式求得,第二项可以利用错位相减法求得。
$$
\begin{align}
& h\sum_{k=0}^{h-1}2^k - \sum_{k=0}^{h-1}k2^k \\
& =h2^{h}-h-\sum_{k=0}^{h-1}k2^k \\
& =h2^{h}-h +\sum_{k=0}^{h-1} k2^k - 2\sum_{k=0}^{h-1} k2^k \\
& =h2^{h}-h+2^h - 2-(h-1)2^h \\
& =2^{h+1}-h-2 \\
& =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 $。

上一题 下一题