2.4.20
#
解答
#
官网给出了解答:https://algs4.cs.princeton.edu/24pq/
首先介绍第一种解法。
设叶子结点的高度为 0,根结点的高度为 h。
于是某个结点 sink 时的最大交换次数即为该结点的高度。
故某一层结点的最大交换次数为 该层结点数 × 该层的高度。
于是总交换次数最大为:
h+2(h−1)+22(h−2)+⋯+2h(0)=k=0∑h−12k(h−k)=hk=0∑h−12k−k=0∑h−1k2k
第一项为等比数列的和,第二项为等差数列乘以等比数列的和。
于是第一项可以直接通过公式求得,第二项可以利用错位相减法求得。
hk=0∑h−12k−k=0∑h−1k2k=h2h−h−k=0∑h−1k2k=h2h−h+k=0∑h−1k2k−2k=0∑h−1k2k=h2h−h+2h−2−(h−1)2h=2h+1−h−2=N−h−1≤N
于是交换次数小于 N,比较次数小于 2N。
另一种解法,可以配合官网的图片帮助理解。
首先堆中某个结点最多一路下沉到叶子结点,
最大交换次数就是该结点的高度(记叶子结点的高度为 0)。
考虑根结点一路下沉到叶子结点的轨迹,
设为 a0,a1,a2,…,ak,其中 k 为根结点的高度,a0 是根结点。
a0 下沉后结点顺序变为 a1,a2,…,ak,a0 。
根据下沉的定义,有 a1>a2>⋯>ak>a0 。
因此 a1 下沉时不可能与 a2 交换,而会向另一个方向下沉。
其余结点同理,可以发现每个结点的下沉路径不会与其他结点重合。
一棵完全二叉树共有 N−1 条边,每访问一条边代表进行了一次交换。
故交换次数必定小于 N,比较次数为交换次数的两倍小于 2N。