2.4.23 #

解答 #

简单的 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) \newline & =\sum_{k=0}^{h-1} t^k(h-k) \newline & =h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \newline \end {align*} $$

其中，第一个数列是等比数列，第二个数列是等差数列和等比数列之积，可以利用错位相减法求得，即：

$$ \begin{align*} & h\sum_{k=0}^{h-1}t^k - \sum_{k=0}^{h-1}kt^k \newline & =\frac{h-ht^{h}}{1-t}-\sum_{k=0}^{h-1}kt^k \newline & =\frac{h-ht^{h}}{1-t} -\frac{\sum kt^k - t\sum kt^k}{1-t} \newline & =\frac{h-ht^h}{1-t}-\frac{t(1-t^{h-1})}{(1-t)^2}+\frac{(h-1)t^h}{1-t} \newline & =\frac{h-t^h}{1-t}-\frac{t(1-t^{h-1})}{(1-t)^2} \newline & =\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} \newline & =\frac{h-ht+t^{h+1}-t +1-1}{(1-t)^2} \newline & =\frac{t^{h+1}-1}{(1-t)^2}+\frac{h-ht-t+1}{(1-t)^2} \newline & =-\frac{n}{1-t}+\frac{h}{1-t}+\frac{1}{1-t} \newline & =\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.