问题及解答

a. 通过 buildHeap 最多使用 $2N$ 次比较的事实, 证明堆个数的下界为 $N!/2^{2N}$.

b. 利用 Stirling 公式扩展这个界.

Remark:

关于 Stirling 公式, 参见 问题703

另外,

\[
N! > 2^{2N}=4^N \Leftrightarrow N\geq 9
\]

$N=1$, 只有 1 种

$N=2$, 一种

$N=3$,  两种

$N=4$, 三种

$N=5$, 8 种（$3!+2!$）

$N=6$, 共 $4!-3!+3!+2!=26$ 种

$N=7$,

$N=8$,

$N=9$,

$N$ 个元素的排列总共有 $N!$ 种. 假设我们实现的是最大堆(Max heap). 则对于每种情形都要进行 buildHeap.

而 buildHeap 的过程是从第 $[N/2]$ 个元素开始, 往前一直到第 1 个元素, 每个元素进行下滤（即执行 perculateDown 的过程.）

不同的排列，经过 buildHeap 过程，可能得到相同的堆. 比如, 最简单的由三个元素 $1,2,3$ 可组成 $3!=6$ 个不同的排列, 但是只能得到两个最大堆.