证明左子树最大规模为2n/3#

由于堆是对应一棵完全二叉树，设它有n个结点根结点。 根的左子树结点数≥根结点的右子树结点数 。

对于一个完全二叉树，它的最后一层可能不是完全填满的。为了估计最大规模，假设我们假设左子堆是一个高度为 h 的满二叉树，右子堆是一个高度为 h-1 的满二叉树。

那么左子树的结点数 nl = ∑i∈[0,h] 2^i = 2^(h+1) - 1 ；右子树的结点数 nr = ∑i∈[0,h-1] 2^i = 2^h - 1

总结点数 n = nl + nr + 1 = 2^(h+1) - 1 + 2^h - 1 + 1 = 3*2^h - 1

于是 左子树结点数/总结点数 = 2^(h+1) - 1 / 3*2^h - 1 = 2*2^h - 1 / 3*2^h - 1 < 2*2^h / 3*2^h = 2/3 故左子树最大规模为2n/3。

分析维护堆#

维护堆是一个向下调整（Percolate Down）的过程，如果为大根堆，则判断当前根结点是否满足大于它的左右结点，如不满足，则替换为左右结点中最大的，接着递归以被替换位置为根向下调整。

它的伪代码为：

1
MAX-HEAPIFY(A, i)
2
    l = LEFT(i)
3
    r = RIGHT(i)
4
    if l ≤ A.heap-size and A[l] > A[i]
5
        largest = l
6
    else largest = i
7
    if r ≤ A.heap-size and A[r] > A[largest]
8
        largest = r
9
    if largest ≠ i
10
        exchange A[i] with A[largest]
11
        MAX-HEAPIFY(A, largest)

分析它非常简单，我们之前已经知道了子树最大规模为2n/3，故递归式为： T(n) = T(2n/3) + Θ(1) ；

根据Master Theorem Case 2， $n^{\log_{2/3} 1} = 1 \in \Theta(1)$ ，故 $T(n) = \Theta(\lg n)$

证明：对一个大小为n的堆，MAX-HEAPIFY的最坏情况运行时间为Ω(lgn)#

MAX-HEAPIFY的最坏情况下（是一个小根堆），每个根都需要运行一次MAX-HEAPIFY，此时一条路径上最长的为 $h = \lfloor\lg n\rfloor$ ，故最坏的运行时间为 $\Omega(\lg n)$ 。

证明叶结点下标#

证明: 当用数组表示存储n个元素的堆时，叶结点的下标分别为 $\lfloor n/2 \rfloor +1,\lfloor n/2 \rfloor +2, \ldots, n$ 。

这个很容易证明，我们想最后一个结点为n，它的父母结点p为 $\lfloor n/2 \rfloor$ 。此时有三种情况：

1. 当父母结点p的左孩子为n的时候，且p不在这一层的末尾，那么p+1开始的结点到n都是叶子节点。 例如下图的堆：最后一位结点n的下标为8，值为1，它的父母结点的下标为 $\lfloor n/2 \rfloor = 4$ ，那么从 $\lfloor n/2 \rfloor+1$ 到n的结点(4, 3, 2, 1)它们都是叶子节点。

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2
6
  /
7
 1

2. 当父母结点p的右孩子为n的时候，且p不在这一层的末尾，那么p+1开始的结点到n都是叶子节点。 同理为右结点时，p的下一位一定也是叶子结点。例如：最后一位结点n的下标为9，值为2，它的父母结点的下标为 $\lfloor n/2 \rfloor = 4$ ，那么从 $\lfloor n/2 \rfloor+1$ 到n的结点(4, 3, 2, 1, 2)它们都是叶子节点。

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2
6
  / \
7
 1   2

3. 当父母结点p的右孩子为n的时候，且p在这一层的末尾，那么p+1开始的结点到n都是叶子节点。 此时这种情况下像之前所知的无论最后一位是左右都无所谓，父母结点的下一个就在最后一位的这一层，它们都是叶子结点。例如：最后一位结点n的下标为7，值为2，它的父母结点的下标为 $\lfloor n/2 \rfloor = 3$ ，那么从 $\lfloor n/2 \rfloor+1$ 到n的结点(5, 4, 3, 2)它们都在最后一层，是叶子节点。

1
        8
2
      /   \
3
     7     6
4
    / \   / \
5
   5   4 3   2

上述为理解证明，但实际上证明可以使用反证法来证明：

假设 $\lfloor n/2 \rfloor+1$ 不位于最后一层，那么它一定有左孩子，其左孩子结点下标小于等于n。

我们证明它的左孩子： $\text{LEFT}(\lfloor n/2 \rfloor+1) = 2(\lfloor n/2 \rfloor+1)$ 因为 $(n/2-1) \leq \lfloor n/2 \rfloor \leq n/2$ ，那么 $2(\lfloor n/2 \rfloor+1) \geq 2(n/2-1+1) = n$ ，此时它的左孩子一定大于等于n，假设不成立得证。

证明在高h的层上至多的结点数#

首先，我们先回顾：从根到节点的简单路径的长度是树中节点的 深度 。树的 高度 是从节点到叶子的最长下行路径上的边数，树的高度是它的根的高度。这意味着，高度从下往上依次是0H，而深度则是从上往下依次是0H。

有了上一个证明，我们知道 n元堆的叶结点的下标分别为 $\lfloor n/2 \rfloor +1,\lfloor n/2 \rfloor +2, \ldots, n$ 。

那么叶子结点的总数有： $n - (\lfloor n/2 \rfloor +1) + 1 \geq \lceil n - n/2 \rceil = \lceil n/2 \rceil$

设高度为h的层有 $n_h$ 个结点，那么高度为0的层，它至多有 $\lceil n/2 \rceil$ 个叶子结点，因为当叶子结点全都在最后一层时成立。

那么使用数学归纳法：在高度为h的层有 $n_h$ 个结点， $n_h \leq \lceil n/2^{h+1} \rceil$ ，

则在高度为h+1的层的结点数为 $n_{h+1} \leq \lceil n_h/2 \rceil = \lceil n/2^{h+1} /2 \rceil = \lceil n/2^{h+1} /2 \rceil = \lceil n/2^{h+1 + 1} \rceil$ 得证。

故 在高h的层上至多的结点数为 $\lceil n/2^{h+1} \rceil$ 。

建堆分析#

我们知道对于一颗完全二叉树， 根的左子树结点数≥根结点的右子树结点数 。那么当它满的时候，这棵树的高度为 $\lfloor\lg n\rfloor$ 。

下面是建堆的代码：

1
BUILD-MAX-HEAP(A, n)
2
    A.heap-size = n
3
    for i = floor(n/2) down to 1
4
        MAX-HEAPIFY(A, i)

这个算法是从最后一个结点的父母结点开始，不断向上调整的过程。在每个 MAX-HEAPIFY(A, i) 中，它的时间复杂度看作是节点i到叶子节点的路径长度，这个路径长度等于这个节点的高度。因此，对于一个高度为h的节点，它的时间复杂度为O(h)。

在一个高度为 $H = \lfloor\lg n\rfloor$ 的完全二叉树中，高度为h的节点有 $2^{H-h} = 2^{\lfloor\lg n\rfloor-h} = 2^{\lfloor\lg n\rfloor}/2^h$ 个。根据之前的证明可以得到 $2^{\lfloor\lg n\rfloor}/2^h \leq \lceil n/2^{h+1} \rceil$

设c为渐近符号中隐含的常数，故整个的时间复杂度为：

$\text{When }0<x<1$, $\sum_{n=0}^{\infty} x^n = 1 / (1 - x)$ 。

对这个公式两边同时求导(对x)，得到 $\sum_{n=0}^{\infty} n \times x^{n-1} = 1 / (1 - x)^2$ ，我们带入 $x = 1/2$，得到 $\sum_{n=0}^{\infty} n \times (1/2)^{n-1} = 1 / (1 - 1/2)^2 = 4$ 。

将两边同时乘以 $(1/2)^2$ ，得到 $\sum_{n=0}^{\infty} n \times (1/2)^{n+1} = 1$ 。

回到原题中，这里的 $\sum_{h=0}^{\infty} h/2^{h+1} = h \times (1/2)^{h+1} = 1$ . 故有：

于是乎建堆的过程，时间复杂度为 $O(n)$ 。

分析堆排序#

1
HEAPSORT(A, n)
2
    BUILD-MAX-HEAP(A, n)
3
    for i = n downto 2
4
        swap(A[1], A[i])
5
        A.heap-size = A.heap-size - 1
6
        MAX-HEAPIFY(A, 1)

对于堆排序，它的过程就非常简单了，因为有n-1次循环，每次MAX-HEAPIFY(A, 1)的时间复杂度为 $O(\lg n)$ ，堆排序的时间复杂度为 $O(n \lg n)$

编写MIN-HEAPIFY(A,i)#

维护堆是一个向下调整（Percolate Down）的过程，根据大根堆的思路，很容易知道小根堆的思路为找到i结点的左右结点，判断i结点是否为最小的，不是则替换，并递归被替换的位置。

于是它的伪代码：

1
MIN-HEAPIFY(A, i)
2
    l = LEFT(i)
3
    r = RIGHT(i)
4
    if l ≤ A.heap-size and A[l] < A[i]
5
        smallest = l
6
    else smallest = i
7
    if r ≤ A.heap-size and A[r] < A[smallest]
8
        smallest = r
9
    if smallest != i
10
        exchange A[i] with A[smallest]
11
        MIN-HEAPIFY(A, smallest)

使用循环重写MAX-HEAPIFY#

我们可以用循环来替换递归来提高效率。当最后的 largest == i 时，我们结束循环。 于是就有：

1
MAX-HEAPIFY(A, i)
2
    while true
3
        l = LEFT(i)
4
        r = RIGHT(i)
5
        if l ≤ A.heap-size and A[l] > A[i]
6
            largest = l
7
        else largest = i
8
        if r ≤ A.heap-size and A[r] > A[largest]
9
            largest = r
10
        if largest == i
11
            return
12
        exchange A[i] with A[largest]
13
        i = largest

证明比较排序的下界#

对于一棵每个排列都是一个可达的叶结点的决策树来说，树的高度完全可以被确定。考虑一棵高度为h的决策树，它对应一个对n个元素所做的比较排序。

对于n个变量的问题，这n个变量有n!种可能的顺序，它在决策树中就有n!个叶结点。根据图中情况可以知道，若为满二叉树，在h层有 $2^h$ 个叶子结点，明显 $n! \leq 2^h$ 。

两边取对数得： h >= lg(n!)

根据Sterling 近似公式，有 n! ≈ √(2πn)(n/e)^n => n! > (n/e)^n 带入可得， h ≥ lg(n/e)^n = n lg(n/e) = n lg n - n lg e = Ω(n lg n)

分析桶排序#

桶排序的步骤为：

1. 根据A数组新建B链表数组，并初始化为0。
2. 将A数组中的元素依次按照一定的规则插入到桶中。（有点像散列表）。
3. 对每个桶内部进行插入排序，当插入排序规模很小的时候，趋向于 $\Theta(n)$ 。
4. 按顺序输出每个桶（桶设置时是有序的）。

它的伪代码：

1
BUCKET-SORT(A, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        insert A[i] into list B[⌊n · A[i]⌋]
7
    for i = 0 to n - 1
8
        sort list B[i] with insertion sort
9
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
10
    return the concatenated lists

在最坏的情况下(所有的数据都插到同一个桶中)，我们发现除了插入排序外，其他的均为 $\Theta(n)$ 。因为插入排序的时间代价为平方阶的，那么整体的桶排序时间代价为： $T(n) = \Theta(n) + \sum_{(0,n-1)}O(n^2)$

我们计算平均的运行时间，对这个式子取数学期望(mean)：

$E( T(n) )= \Theta(n) + E (\sum_{(0,n-1)}O(n_i^2) )$ $= \Theta(n) + \sum_{(0,n-1)}O( E(n_i^2) )$

一共有n个桶，这个数据落入这个桶的概率为1/n，数据落入桶这个过程它满足二项分布 $n_i \sim B(n,1/n)$

$E( T(n) )= \Theta(n) + \sum_{(0,n-1)}O( E(n_i^2) )$ $= \Theta(n) + \sum_{(0,n-1)}O( 2 - 1/n )$ $= \Theta(n) + O(n)$ $= \Theta(n)$

因为在二项分布中：

• $E(x) = np = 1;$
• $Var(x) = np(1-p) = 1 - 1/n;$
• $E(x^2) = Var(x) + E^2(x) = np(1-p) + (np)^2 = 1 - 1/n + 1 = 2 - 1/n;$

故平均情况下为 $\Theta(n)$ 但最坏的情况为 $\Theta(n^2)$ ，因为插入排序最差情况为 $\Theta(n^2)$

修改计数排序#

设由n个元素组成的输入序列每个元素都是区间[0: k]内的一个整数，且这些元素没有卫星数据，修改COUNTING-SORT，只用数组 A和C，将输出序列放在A中。

这样输入序列所有元素只能从 C 中复制，修改后COUNTING-SORT的伪代码如下：

1
COUNTING-SORT(A, n, k)
2
    let C[0:k] be new arrays
3
    for i = 0 to k
4
        C[i] = 0
5
    for j = 1 to n
6
        C[A[j]] = C[A[j]] + 1 // C[i] now contains the number of elements equal to i.
7
    p = 1
8
    for i = 0 to k
9
        while C[i] > 0
10
            A[p] = i
11
            p = p + 1
12
            C[i] = C[i] - 1

基于CDF的桶排序#

设X为一个随机变量，设它的累计分布函数(CDF)为F(x) = P(X≤x)，设 $X_1,X_2,\ldots, X_n$ 服从F(x)，且在 $O(1)$ 时间内可以计算得到(若给定 y 和 F(x)=y，能够在 $O(1)$ 时间内计算出x )，设计一个算法，能在平均情况为线性时间内完成排序。

这样的算法我们可以使用桶排序，设置F(x) = i/n，有n个桶，它们就满足二项分布了，这个就和桶排序基本一致，于是我们的伪代码可以写为：

1
BUCKET-SORT(X, n)
2
    let B[0 : n - 1] be a new array
3
    for i = 0 to n - 1
4
        make B[i] an empty list
5
    for i = 1 to n
6
        if x_{i-1} ≤ X_i and X_i < x_i
7
        insert X_i into list B[i-1]
8
    for i = 0 to n - 1
9
        sort list B[i] with insertion sort
10
    concatenate the lists B[0], B[1], ... , B[n - 1] together in order
11
    return the concatenated lists

其中， $x_i$ 是满足 $F(x_i) = i/n$ 的值，可以在 $O(1)$ 时间内计算得到。由于输入数据服从分布F(x)，每个桶期望包含的元素数量为1，因此平均情况下算法的时间复杂度为 $\Theta(n)$ 。