2.4.23

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

解答

简单的 sink 实现

sink 方法会在所有的 $ t $ 个子结点中寻找最大的结点。
如果找到的结点比当前结点大,那么就进行交换。
否则视为结点已经下沉到了合适的位置,结束循环。
根据题意,在 $ t $ 个元素中找最大值需要 $ t $ 次比较。
sink 操作需要找到 $ t $ 个子结点中的最大值并与当前结点相比较。
于是 sink 操作每次最多需要 $ t + 1 $ 次比较。

建堆过程,对 2.4.20 的证明进行推广。
设 $ t $ 叉树的高度为 $ h $ ,叶子结点的高度为 $ 0 $,根结点的高度为 $ h $。
根据 sink 操作的定义,高度为 $ k $ 的结点最多进行 $ k $ 次交换(到达叶子结点)。
于是建堆需要的总交换次数为:
$$
\begin{align*}
& h+t(h-1)+t^2(h-2)+ \dots + t^h(0) \\
& =\sum_{k=0}^{h-1} t^k(h-k) \\
& =h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \\
\end {align*}
$$

其中,第一个数列是等比数列,第二个数列是等差数列和等比数列之积,可以利用错位相减法求得,即:
$$
\begin{align*}
& h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \\
& =\frac{h-ht^{h}}{1-t}-\sum_{k=0}^{h-1}kt^k \\
& =\frac{h-ht^{h}}{1-t} -\frac{\sum kt^k - t\sum kt^k}{1-t} \\
& =\frac{h-ht^h}{1-t}-\frac{t(1-t^{h-1})}{(1-t)^2}+\frac{(h-1)t^h}{1-t} \\
& =\frac{h-t^h}{1-t}-\frac{t(1-t^{h-1})}{(1-t)^2} \\
& =\frac{h-ht+t^{h+1}-t}{(1-t)^2}
\end{align*}
$$
考虑到对于 $ t $ 叉堆,结点数可以表示为 $ n=\frac{t^{h+1}-1}{t-1} $ 。故交换次数可以化简为:
$$
\begin{align*}
& \frac{h-ht+t^{h+1}-t}{(1-t)^2} \\
& =\frac{h-ht+t^{h+1}-t +1-1}{(1-t)^2} \\
& =\frac{t^{h+1}-1}{(1-t)^2}+\frac{h-ht-t+1}{(1-t)^2} \\
& =-\frac{n}{1-t}+\frac{h}{1-t}+\frac{1}{1-t} \\
& =\frac{n-h-1}{t-1} \le n
\end{align*}
$$

故建堆所需比较次数最大为 $ (t+1)n $ 。
每次删除最大元素都会对根结点调用一次 sink 操作,
因此排序所需的比较次数最多为 $ (t+1)n\log_t(n) $ 。
相加得堆排序所需的总交换次数最多为 $ (t+1)n + (t+1)n\log_t(n) =(t+1)(n\log_tn+n) $ 。
利用换底公式将对数的底换成 2,得到:$ \frac{t+1}{\lg t} n\log n $ 。
于是问题变为求 $ f(t)= \frac{t+1}{\lg t} $ 的最小值,对其求导,得到:
$$
( \frac{t+1}{\lg t} )’=\frac{-t+t\ln t-1}{t\ln^2t}·\ln 2
$$
直接求导数的零点会比较困难,但利用勘根公式可以寻找到根所在的区间。
由于 $\ln 2$ 不影响正负,我们直接将其去掉,变为:
$$
\frac{-t+t\ln t-1}{t\ln^2t}=\frac{-1+\ln t-\frac{1}{t}}{\ln^2t}
$$
由于 $ t > 1 $,分母总是为正,因此导函数正负就等于下面这个函数的正负:
$$
\begin {align*}
g(t)=\ln t -1-\frac{1}{t}
\end {align*}
$$
$ t = e $ 时 $ g(t) < 0 $,$ t=e+1 $ 时 $ g(t) > 0 $。于是可以求得在 $ (e, e+1) $ 上 $ f(t) $ 存在极小值。
又由于 $ g(t) $ 在 $ (e + 1, +\infty) $ 始终为正,因此在 $ (e, e+1) $ 上存在的是最小值($ t \ge 2 $)。
因为 $ t $ 为大于 $ 1 $ 的正整数,且 $ f(4) < f(3) $,故 $ t=4 $ 时系数最小,此时系数为 $ 2.5 $ 。

Floyd 方法

在删除最大元素的过程中,根结点会和最后一个结点交换,然后对新的根结点执行 sink 操作。
大多数情况下,这个结点会被一路交换到树的最后一层。
因此我们省去 sink 操作中与自己比较的过程,直接和子结点中的较大者进行交换。
这样一路交换到树的底部,随后再让这个结点与自己的父结点比较,向上「回到」合适的位置。
大多数结点都不需要向上交换,
因此这样的优化可以减少比较次数(下降一层需要的比较次数从 $ t+1 $ 变为 $ t $)。

利用 Floyd 方法对于建堆没有影响(建堆也可以使用 Floyd 方法,参见「另请参阅」部分)。
于是建堆的比较次数仍为 $ (t+1)n $ 。
排序的比较次数变为 $ tn\log_t(n) $ 。
总的比较次数变为 $ (t+1)n + tn\log_t(n) $ 。
我们仍然只关心 $n\lg n$ 的系数,系数为 $ f(t)= \frac{t}{\lg t} $ 。
按照之前的方法再求一次最小值,求得 $ t = 3 $ 时系数最小,此时系数为 $ 1.89 $ 。

另请参阅

Floyd 提出的堆排序优化
Floyd R W. Algorithm 245: treesort[J]. Communications of the ACM, 1964, 7(12): 701.
通过将这种方法应用到建堆获得的快速建堆方法
McDiarmid C J H, Reed B A. Building heaps fast[J]. Journal of algorithms, 1989, 10(3): 352-365.

上一题 下一题