13. 红黑树

二叉搜索树的各种操作时间复杂度为$\Omicron(h)$，但是树的高度h不可控，最差的情况为n。
而平衡搜索树能将树的高度控制在$\Omicron(\lg(n))$。
常见的平衡搜索树有：

• AVL树
• 红黑树
• treap （tree + heap，给每个元素随机的priority，从而间接的实现随机插入，使得树的期望高度为$\Omicron(\lg(n))$）
• B树 （十八章介绍）
  • 2-3-4树

本章重点讨论红黑树，以及习题中出现的AVL树。AVL树较为简单所以先介绍AVL树。

AVL树

AVL树由Adel’son-Vel’skii & Landis 在1962年发明，由他们的名字命名。
比较一般的二叉搜索树，每个结点额外存储它的高度，nil的高度为0，其他节点的高度为Height(x) = max(Height(x->left), Height(x->right)) + 1。每个结点两个孩子的高度差不能超过1。
当右子树的高度比左子树的高度高时，我们称right-heavy（如下图），反之这称left-heavy。

AVL树的各种查询操作都和普通二叉搜索树无异，所以我们只需关注会改变树结构的Insert操作和Delete操作。
在一般的Insert或者Delete操作后，结点的高度会变，所以有可能会违反AVL树的性质，这时候我们需要引入一个操作Rotate（旋转）

Rotate

旋转分为两种，左旋（LEFT-ROTATE）和右旋（RIGHT-ROTATE）。下图右测变为左侧的情况称为对x结点左旋，左侧变为右侧的情况称为对y结点做右旋。

我们可以发现旋转操作并不会影响二叉搜索树的性质。
旋转前后都会保持α <= x <= β <= y <= γ
下面是左旋的伪代码，右旋的操作和左旋对称，不再赘述。

Ref：AVLTree::LeftRotate & AVLTree::RightRotate in AVLTree.h

AVL树平衡调整（ADJUST_FROM(x)）

当Insert或者Delete一个元素后，平衡有可能被破坏，假设x是最底层被破坏性质的节点，而且是right-heavy时（left-heavy是对称的）：

1. Balance
   • 如果x的右孩子y是平衡的或者right-heavy的（Figure 5）
     • 我们对x做LEFT-ROTATE操作可使其恢复平衡
     • 然后重新计算x和y的高度
   • 如果x的右孩子z是left-heavy的（Figure 6）
     • 我们先对z做RIGHT_ROTATE，然后对x做LEFT-ROTATE，可使其恢复平衡
     • 然后重新计算x，y，z的高度
2. Loop
   • 重新计算x的高度，并使得x=x->p继续循环，直到根节点
   • 若图中发现某节点不平衡的用1. Balance

Ref：AVLTree::AdjustFrom in AVLTree.h

AVL树 Insert

因为插入的节点肯定是叶子节点，所以直接对插入节点调用ADJUST_FROM(x)即可。

Ref：AVLTree::Insert in AVLTree.h

AVL树 Delete

删除操作略为复杂，可能会影响子节点的平衡。

• 当被删除节点只有一个孩子，或者没有孩子时，被删除节点的孩子不会被应用
  • 这时对删除节点原来的父节点调用ADJUST_FROM(x)即可
• 当被删除节点有两个孩子时
  • 如果被删除节点右子树的最小节点min的父节点为被删除节点，这时对min调用ADJUST_FROM(x)
  • 其他情况，对min原来的父节点调用ADJUST_FROM(x)

Ref：AVLTree::Delete in AVLTree.h

红黑树

红黑树也是一种平衡二叉树。它在每个节点上增加一个存储位color来表示节点的颜色，节点的颜色为RED或者BLACK。通过对任何一条从根节点到叶子节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，所以是近似于平衡的。
红黑树还定义一种NIL节点，NIL节点是红黑树的叶子结点（外部节点），真实的数据组成树的内部节点（如下图a所示）。
红黑树的具体性质如下：

1. 每个节点不是红色的就是黑色的
2. 根节点是黑色的
3. 每个叶结点（NIL）是黑色的
4. 如果一个结点是红色的，那么它的两个孩子都是黑色的
5. 对于每个结点，从该结点到其所有后代叶结点的简单路径上，黑色结点的数量相同

为了方便处理，使用一个哨兵来替代NIL结点。对于一颗红黑树T，哨兵T.nil是一个普通结点。它的color为BLACK，用哨兵T.nil替换图a中的所有NIL，这样就形如下图b所示，T.nil的p, left, right, key属性我们并不关心，所以方便起见程序中可以对其值随意设定。

为了方便起见，我们在图中省去T.nil，这样就变成了图c的样子。

NULL -> T.nil

红黑树与普通二叉搜索树相比，用T.nil替代了空指针。
所以所有操作中用到空指针的地方，需要换成T.nil。后面不做赘述。

红黑树 Insert

红黑树的插入操作，除了一般的操作外，还需要把插入结点的颜色设为RED。因为插入了一个红色的结点，所以有可能触犯红黑树的一些性质（1,4），所以我们要调用RB-INSERT-FIXUP将其修正。

RB-INSERT-FIXUP会循环的查看z的父结点是否违反性质4，如果违反，则将其修正。如果修正后仍然有可能违反性质4，则继续循环查看其爷结点。（本文只讨论插入结点的父结点为爷结点的左孩子的情况，右孩子的情况与其对称，不再赘述。）

修正过程有三种情况：

• Case 1. z的叔结点为红色
• Case 2. z的叔结点为黑色，且z是父亲的右孩子
• Case 3. z的叔结点为黑色，且z是父亲的左孩子
  

上图插入4之后的处理过程。下面我们详细讨论下三种情况的处理方式：

• Case 1
  这种情况只需改变着色，将父节点和叔结点染成黑色，爷结点染成红色。
  因为爷结点以前是黑色，却染成了红色，如果爷结点的父结点为红色，这时仍会触犯性质4，所以我们将爷结点赋给z，下次循环时再修正它。
  如果z的爷结点为root结点，我们修正后root结点变成了红色，并且让z指向root结点然后跳出了循环。在循环外边我们会将z重新染成黑色，所以保持了性质1。
  

• Case 2/3
  当z是父结点的左孩子时，符合Case 3，这时我们只需把爷结点做右旋，然后交换之前父结点和爷结点的颜色。这时局部的根节点颜色没有改变，仍然是黑色，所以整个树都满足了红黑树的特性，无需继续循环。
  
  当z是父结点的右孩子时，符合Case 2，这时只需要对父结点做左旋，使其变为Case 3的情况。

由上可知，一旦循环进入Case 2或者Case 3，就会结束循环。所以一次插入操作最多只会有两次旋转操作。尽量少的循环操作是非常有益的，因为改变结点颜色并不会影响查找功能，当多线程处理时我们只需给旋转操作加锁。

红黑树 Delete

删除操作比插入操作略微复杂，当删除一个黑色结点，或者删除过程中移动了一个黑色结点时，都有可能破坏红黑树的性质（2,4,5）。

当被删除的结点只有一个孩子，或者没有孩子，这时我们只需关心被删除结点的颜色，如果被删除的结点为红色，则无需修正，如果被删除结点为黑色，则需要从被删除结点的孩子开始修正。

当被删除的结点有两个孩子时，我们会找右子树的最小结点来替代被删除结点的位置和颜色，所以这是我们需要关注这个最小结点的颜色，如果最小结点的颜色为红色，则无需修整，如果这个最小结点为黑色，则需要从最小结点的右孩子开始修正。

从x开始修正时，有五种情况：

• Case 0. x为红色
  • 这时23行会将其设为黑色，可直接满足所有红黑树性质
• Case 1. x的兄弟结点w为红色
• Case 2. x的兄弟节点w为黑色，且w的两个孩子都是黑色
• Case 3. x的兄弟节点w为黑色，且w的右孩子为黑色，左孩子有红色
• Case 4. x的兄弟节点w为黑色，且w的右孩子为红色

• Case 1
  这种情况我们将其转换为Case2/3/4

  1. 设置兄弟节点w为黑色，父结点为红色
  2. 左旋父结点
  3. 重新设置w为x的兄弟结点

• Case 2
  这种情况将兄弟结点w设置为红色，并且x=x.p，继续循环。
  我们会发现，如果是从Case 1转换到Case 2，那么x.p一定是红色，所以会直接退出循环。

• Case 3
  这种情况我们将其转换为Case4

  1. 设置兄弟节点w为红色，w的左孩子为黑色
  2. 右旋w结点
  3. 重新设置w为x的兄弟结点

• Case 4
  这种情况可以做一些修改，然后结束修正

  1. 设置w的颜色为x父结点的颜色
  2. x父结点的颜色设置为黑色
  3. w右孩子的颜色设置为黑色
  4. 左旋x的父结点
  5. 使x指向root结点，从而结束修正

由上可知，一旦循环进入Case 1, Case 3，Case 4，就会结束循环。所以一次插入操作最多只会有三次旋转操作（Case 1 -> Case 3 -> Case 4）。

性质维护:

插入过程中维护性质的分析：

1
2

Case1 转换后，局部的黑高与之前相同
但是由于将局部根节点C从黑色变成红色，所以需要继续考虑C是否违反性质4

1
2

Case2/3 转换后，局部的黑高与之前相同
并且局部根节点B的颜色没有改变，所以直接Done

删除过程中维护性质的分析：

需要修正时，被修正结点x以前的父节点肯定为黑色，x替代了x以前父节点的位置
所以这时这个子树（x为根节点）的黑高减少了1

1
2
3
4

Case1 转换后，ABCDE的黑高都没有变
所以这时仍然是x为根节点的子树黑高少1

根本情况没有变化，变化的只是x的兄弟节点的颜色

1
2
3
4
5

Case2 转换后，以x的父节点c为根节点的子树已经满足红黑树的性质
但是c为根节点的子树的黑高比之前少1

所以令c为新的x，继续调整

1
2
3
4
5

Case3 转换后，ABCDE的黑高都没有变
所以这时仍然是x为根节点的子树黑高少1

根本情况没有变化，变化的只是w的右孩子的颜色

1
2
3
4
5

Case4 转换后，以c为根节点子树满足红黑树性质
并且根节点的颜色没有变化，子树的黑高也没有变化

所以Done

涉及数据结构

点击查看实现

• AVL树
• 红黑树

留言與分享

12. 二叉搜索树

二叉搜索树支持许多动态集合的操作，包括Search，Insert，Delete，Minimum，Maximum，Successor，Predecessor。所有操作的时间复杂度为$\Omicron(h)$，h为树的高度。

二叉搜索树

二叉搜索树是一个链式存储的二叉树，且具有如下特性：
设x为二叉搜索树中的一个结点。

• 如果y是x左子树中的一个结点，那么y.key<=x.key。
• 如果y是x右子树中的一个结点，那么y.key>=x.key。

Search

从根节点开始查找，如果查询的k小于根节点的key，则递归查找左子树；如果查询的k大于根节点的key，则递归查找右子树；如果查询的k等于根节点的key，done。

Minimum

从根节点开始沿着left child方向一直找到低。

Maximum

从根节点开始沿着right child方向一直找到低。

Successor & Predecessor

查询x的下一个节点：

• 如果x有右孩子，那么x的下一个节点就是右子树的最小值。

  1 2 3 4 5 6 7

  ○ / \ ● / \ ○ / \ [○]

• 若果x没有右孩子，那么x的下一个节点是x的第n个parent，这个parent是第一个符合下图的情况，第n-1个parent 是第n个parent得 left child。

  1 2 3 4 5 6

  [○] / \ ○ / \ ● /

• 如果没有符合这样情况的parent，那么说明x是最大数，没有下一个节点。

Insert

上图描述了插入key为13的数据。
从根节点x开始查找。如果待插入数据小于该节点数据，到左子树继续查找，否则到右子树查找，直到找到一个空位置，将数据放入。

Delete

删除操作的情况较为复杂，有如下几种情况

1. 待删除节点没有孩子
2. 待删除节点只有一个孩子，如下图(a) (b)情况
3. 待删除节点有两个孩子，并且右孩子没有左孩子时，如下图©情况
4. 待删除节点有两个孩子，并且右孩子有左孩子时，如下图(d)情况

1. 当待删除节点没有孩子时：
   • 可以直接删除该节点，并且修改他的父节点，用nil代替他
2. 当待删除节点只有一个孩子时，如图中 (a) (b) 情况：
   • 可以直接用子节点替换该节点
3. 当待删除节点有两个孩子时，如图中 © (d) 情况：
   • 思路：用待删除节点z的Successor节点y替代它的位置
   • 情况c，右孩子没有左孩子（y是z的子节点）
     • y替换z，并且接管z的左孩子
   • 情况d，右孩子有左孩子
     • y的右孩子x替换y，并且y接管z的右孩子
     • y替换z，并且接管z的左孩子

Tips：当待删除节点有两个孩子时，用待删除节点的Predecessor节点替代它也可以。

涉及数据结构

点击查看实现

• 二叉搜索树

留言與分享

11. 散列表（哈希表）

许多应用都需要一种动态集合，至少支持Insert，Search和Delete的字典操作。
散列表（Hash Table）是实现字典操作的一种有效数据结构。尽管最坏情况下散列表查询一个元素的时间和链表的查询时间相同，为Θ(n)。但是在实际应用中，散列表的查询性能是极好的。在一些合理的假设下，散列表中扎寻一个元素的平均时间能为Ο(1)。

假设某应用需要用到一个动态集合，其中每个元素的KEY都是取自全域U={0, 1, …, m-1}。本章讨论方法都是基于这样的动态集合。

直接寻址表

当KEY的全域U较小时，直接寻址表是一种简单而有效的技术。
为了表示这个动态集合，我们用一个数组作为直接寻址表，记为T[0…m-1]，其中数组的每个位置称为槽，与全域U中的KEY一一对应。
K集合表示实际存在的元素的KEY集合。
槽k指向KEY为k的元素，如果K集合中没有k，那么T[k] = nil。

散列表

直接寻址表的缺点很明显：

1. 如果全域U非常大，则计算机无法存储
2. 如果K集合相对于全域U非常小，那么将非常浪费空间

如果直接寻址表占用的存储空间为$\Theta(|U|)$，那么散列表能将存储需求降至$\Theta(|K|)$，同时散列表中查找一个元素的时间为$\Omicron(1)$，不过是平均时间。

散列方式不同于直接寻址表的地方是，元素存储在散列表中的位置由散列函数决定，即k元素存储在散列表的h(k)位置。h(k)叫做k的散列值。

散列表T的大小比|U|小很多，所以肯定会有冲突的情况。

冲突最简单的解决方式是使用链接法，后面还介绍一种开放寻址法。
下图是链接法的图示，当有两个k值映射到了同一个散列值时，将它们保存在一个链表内。

链接法散列分析

如果要将n个数据存储在m大小的散列表中，我们称α = n/m为装载因子，即散列表的每个槽平均存放的数据。
假设散列函数能等可能的把数据散列到m个槽中，我们称这个假设为简单均匀散列。
这时每个槽存放元素个数的期望值为α。

所以，一次不成功查找的平均时间为$\Theta(1+\alpha)$。（1 表示散列函数消耗的时间）

1

因为每个槽的期望为α，而不成功的情况下，查找的期望时间就是从槽链表的头遍历到链表尾，所以期望时间就是槽链表的长度α。

一次成功查找的平均时间为$\Theta(1+\alpha)$。

1
2

具体证明参考公开课中老师的推理，或者书中推理。
自我理解：一个元素在槽中的位置是等概率随机的(1/α)，而且期望时间为元素在槽中位置的期望。期望位置为(1+2+..+α)*(1/α) = (α+1)/2

散列函数

最好的散列函数便是能达到简单均匀散列。
下面介绍一些的散列函数。其中全域散列能够达到这样的要求。

除法散列

1

h(k) = k mod m

m最好是一个素数，并且不能太接近2或者10的乘方。

乘法散列

1

h(k) = [(a * k) mod 2^w] >> (w − r)

k是w bits的数
m = 2^r
a最好是一个奇数，并且不能太接近2或者10的乘方。

全域散列

随机的选择散列函数，称为全域散列
Example：

1
2

h(k) = [(ak+b) mod p] mod m 
where a and b are random ∈ {0, 1, . . . p−1}, and p is a large prime (> |U|).

证明全域散列为简单均匀散列的过程，参考公开课中老师的推理，或者书中推理。

开放寻址法

• 无链表，所有的元素都保存在table中
• 每个槽存储一个元素，m>=n
• 散列函数为h(k, i)，i从0开始，当有冲突后i++，直到找到一个空的位置，所以散列函数需要有如下性质：

1
2
3
4
5

对同一个KEY做m次探查，能把散列表填满

h : U × {0, 1,...,m − 1} → {0, 1,...,m − 1}

{h(k, 0), h(k, 1), . . . , h(k, m − 1)} == {0, 1,...,m − 1}

删除时，不能直接删除！删除后需要标记此位为删除位。

线性探查

1

h(k, i) = (h1(k) +i) mod m

双重探查

1
2
3
4

h(k, i) =(h1(k) + i·h2(k)) mod m

h2(k) 需要和 m 互为质数
e.g. m = 2^r, h2(k) 永远为奇数

开放寻址法分析

给定一个装载因子α = n/m < 1的开放寻址散列表，并假设是均匀散列的：
对于一次不成功的查找，期望的探查次数至多为1/(1-α)
对于一次成功的查找，期望的探查次数至多为\frac{1}{α}\ln(1/(1-α))

完全散列

基于全域散列，完全没看。。。

涉及数据结构

点击查看实现

• 使用链接法的散列表

留言與分享

10. 基本数据结构

动态集合的基本数据结构。

栈

栈，后进先出，用数组存储，并用top保存栈顶位置。支持压入（Push）和弹出（Pop）操作。
a->b产生了两次Push操作，压入了17和3。
b->c产生了一次Pop操作，弹出了3。

队列

队列，先进先出，用数组存储，用head和tail保存队列的头和尾的位置。支持入队（Enqueue）和出队（Dequeue）操作。
a->b产生了三次Enqueue操作，加入了17 3 5。
b->c产生了一次Dequeue操作，去除了15。
当head或者tail超出数组范围时，转移到数组头部。
当tail等于head时，表示队列已满，不能再加入数据。

链表

链表是一种对象按照线性排序的数据结构，不同于数组的是链表的顺序由各个对象里的指针表示。
下图表示一个双向链表。每个对象包含prev指针，next指针，key值，或者附加一些卫星数据。
prev指针指向上一个对象
next指针指向下一个对象
用一个head指针指向头结点，头结点的prev指针为null
尾结点的next指针为null

单向链表为双向链表去除prev指针。

下图是一个带有哨兵的双向循环链表，说实话没看出这个哨兵的必要性。

数组存储链表

不是所有的语言都支持指针，所以只能间接实现链表。
下图给出一种用多个数组存储链表的方式，next数组和prev数组中存储next元素或prev元素的数组下标，从而间接的实现了双向链表。

为了更方便快捷的在分配和释放数组中的元素，在数组中存储一个free单向连边。
当需要分配元素时，分配free链表的头结点，并使free指向下一元素。
当需要释放元素时，使该元素的next指向free指向的元素，并使得free指向该元素。

二叉树

前面我们讨论过一种特殊二叉树——堆的存储，我们将堆存储在数组中。
但对于一般的二叉树，我们将用链式数据结构表示。

每个元素包含三个指针——p、left、right分别指向父节点、左孩子、右孩子。
根节点的p指向null，叶子节点的left和right指向null。

当我们需要存储一个N叉树时，按照上面的方法，每个元素则需要child1、child2…childN来存储，会占用很多额外空间，如果孩子个数是未知的这种方式则无法实现。
下图展示了一种分支无限制的有限树的存储方式——左孩子右兄弟表示法。left指向第一个孩子，right指向兄弟节点。

涉及数据结构

点击查看实现

• 双向链表

留言與分享

9. 中位数和顺序统计量

顺序统计量，第i个顺序统计量指n个元素集合中第i小的元素。
最小值，第1个顺序统计量。
最大值，第n个顺序统计量。
中位数，第n/2个顺序统计量。（若n为偶数，取n/2-1）

我们可以通过一次遍历数组，取得最大值或者最小值。
但是若要取得中位数或者其他顺序统计量，则没办法通过一次遍历数组得到。
如果将数组排序，将可以直接得到中位数或者任意顺序统计量。由之前所学的排序算法可知，时间复杂度最好为$\Theta(n\lg n)$
本章讨论如何在线性时间找到中位数或者其他顺序统计量。

期望为线性时间的选择算法

利用随机快速排序的思想，随机的挑选一个元素作为主元，并把数组分为两侧，一侧比主元小，一侧比主元大，如果主元的位置q就是想找的顺序统计量的位置i，则返回主元，否则继续递归的查找左侧数组或者右侧数组。伪代码如下：

最坏情况为线性时间的选择算法

这个算法由几个大牛共同完成，发布在论文Time bounds for selection中。

中文描述如下：
https://www.jianshu.com/p/1c021beb5e72

涉及算法

点击查看实现

• 随机选择算法（RANDOMIZED_SELECT）

习题答案

练习

9.3-6

1
2
3

1. 如果k为1时，返回空数组
2. 如果k为偶数，找到数组的中位数,并把数组分为两组（比中位数大的一组，比中位数小的一组），递归解决这两个子问题，并把中位数以及两个字问题的解合并返回
3. 如果k为奇数，找到数组中间的两个分位数left和right，并把数组分出两组（比left小的一组，比right大的一组），递归解决这两个子问题，并把left right以及两个字问题的解合并返回

9.3-7

1
2
3
4

1. 线性时间找到中位数
2. 线性时间算出每个元素和中位数的距离（|x-middle|）
3. 线性时间找到第k小的距离
4. 线性时间找出比k小的距离对应的元素

9.3-8

1
2
3

1. 选择X Y两数组的中位数作为主元Xk和Yk
2. 比较Xk和Yk，如果Xk大于Yk，则取Xk左侧的元素作为新的X数组（包括X），取Yk右侧的元素作为新的Y数组（包括Y）
3. 重复1 2 两部，直到每个数组只剩两个元素，剩下的四个元素中第二小的便是两数组的中位数

留言與分享

8. 线性时间排序

前边介绍了很多排序算法，他们有一个共同点：元素的排序依赖于对他们之间的比较，这类排序我们称其为比较排序。本章节讨论比较排序的下界以及一些线性时间的排序方法。

比较排序的下界

将比较排序抽象为一颗决策树。
下图为三个元素排序的一颗决策树，叶子节点表示比较结果，其他节点表示某两个元素$(a,b)$作比较，节点的左子节点表示$a<=b$，节点的右子节点表示$a>b$。可以发现叶子节点包含了三个元素比较的所有可能情况，而且从根节点到叶子节点用了最少的比较次数。

接下来我们考虑n个元素排序的情况，因为n个元素排序可能会有n!种情况，所以叶子节点树小于等于n!，而这个树高度表示需要最坏情况的比较次数。

$h >= \lg(n!) = \Omega(n\lg n)$

所以在最坏情况下，任何比较排序算法都需要做$\Omega(n\lg n)$次比较。

计数排序

假设n个元素都是0~k之间的整数，而且$k=\Omicron(n)$时，计数排序的运行时间为$\Theta(n)$。

计数排序的基本思想为，首先得到0~k每一个值对应多少个元素，然后推算出每一个值对应元素在输出数组上的位置范围，最后将各个元素放到应该的位置。
计数排序的伪代码和处理过程如下图所示：

基数排序

基数排序的思想为，将带排序的数看做d位数，每一位的取值有K个可能，然后把待排数组从最低位开始做稳定排序（当有相同的数值时，排序后他们的顺序不变），一位接着一位直到最高位。伪代码，以及一个三位十进制数的排序过程如下：

如果基数排序使用的稳定排序方法耗时为$\Theta(n+k)$，每个数为d位，那么基数排序的时间复杂度为$\Theta(d(n+k))$

桶排序

TODO:

涉及算法

点击查看实现

• 计数排序

留言與分享

7. 快速排序

快速排序是一种最坏情况时间复杂度为$\Theta(n^2)$的排序算法，虽然最坏情况的时间复杂度很差，但是快速排序通常是实际排序应用中最好的选择，因为它的平均性能非常好，它的期望时间复杂度是$\Theta(n\lg n)$，而且$\Theta(n\lg n)$中隐含的常数因子非常小。另外它是原址排序。

快速排序

快速排序也用了分治的思想。对子数组A[p…r]进行快速排序的过程如下：
分解 将A[p…r]划分为两个数组A[p…q-1]和A[q+1…r]，使得A[p…q-1]的每一个元素小于等于A[q]，而A[q+1…r]的每一个元素大于等于A[q]。
解决 递归调用快速排序，对子数组A[p…q-1]和A[q+1…r]进行排序。
合并 因为是原址操作，所以无需合并，这时A[p…r]已经有序。

伪代码和分解过程如下：

性能

最坏情况

若每次分解时，都分解为一个空数组和一个n-1大小的数组,则为最坏情况。
递归式为$T(n) = T(n-1) + T(0) + \Theta(n)$
$T(n)$的解为$\Theta(n^2)$

最好情况

若每次分解时，都分解为两个一样大的子问题，这时为最好情况。
递归式为$T(n) = 2 T(n/2) + \Theta(n)$
$T(n)$的解为$\Theta(n\lg n)$

平衡的划分

若每次分解时，都按照一定比例分割，比如按照9:1划分。
递归式为$T(n) = T(9n/10) + T(n/10) + \Theta(n)$
$T(n)$的解为$\Theta(n\lg n)$

可用代入法证明按照任何比例划分，$T(n)$的解都为$\Theta(n\lg n)$

平均情况

若每次分解时，最好情况和最坏情况交替出现。
$T(n)$的解为$\Theta(n\lg n)$

可以将最好情况和最坏情况合并，时间复杂度并没变

随机快速排序

随机快速排序可以避免特定输入（已排序的队列或逆序列）时运行时间较长的情况。
分解时，随机的挑选数组中的一个元素来分解。

TODO: 证明随机快速排序的期望运行时间

涉及算法

点击查看实现

• 快速排序
• 随机快速排序

留言與分享

6. 堆排序

堆排序也是一种时间复杂度为$\Omicron (n\lg n)$的排序算法，但是与归并排序不同的是堆排序是一种原址排序，也就是说排序过程只是交换数据的位置。

最大堆

堆是一个数组，存储一个近似完全二叉树，树上的每个结点对应数组中的一个元素，数组第一个元素存储根节点，第i个元素的左孩子在数组的2i位置，右孩子在数组的2i+1位置，父结点在数组的i/2位置。

最大堆指一种父节点必然大于等于子节点的堆。下图为一个最大堆的存储情况：

MAX-HEAPIFY（维护最大堆）

MAX-HEAPIFY是维护最大堆性质的重要方法。MAX-HEAPIFY的输入为数组A和下标i，当调用MAX-HEAPIFY时，假定根节点为LEFT(i)和RIGHT(i)的二叉树都是最大堆，但是A[i]可能比它的子节点要小。MAX-HEAPIFY通过让A[i]的值在最大堆中逐级下降，从而使得以下标i为根节点的树符合最大堆的性质。以下是MAX-HEAPIFY的伪代码以及MAX-HEAPIFY(A, 2)的处理过程：

因为堆的高度为$\lg n$，所以该过程的时间复杂度是$\Omicron (\lg n)$.

建堆

自下而上的调用MAX-HEAPIFY可以把一个数组转换为最大堆。
叶子节点不需要调用，所以从下标为n/2的的元素开始，一直到根节点。
伪代码和建堆过程如下：

堆排序

1. 利用BUILD-MAX-HEAP方法构建最大堆
2. 接着循环的堆的根节点和最后一个元素交换
3. 堆的大小减一
4. 调用MAX-HEAPIFY(A, 1)
5. 循环2-4步，直到堆中只剩根节点

伪代码，以及2-5步过程如下：

优先队列

堆除了堆排序还有很多应用，比如优先队列。优先队列也有两种最大优先队列和最小优先队列。
一个最大优先队列支持以下操作：

1
2
3
4

INSERT(S, x)
MAXIMUM(S)
EXTRACT-MAX(S)
INCREASE-KEY(S, x, k)

最大优先队列的应用有很多，其中一个是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业及他们之间的相对优先级。
最小优先队列可以被用于基于事件驱动的模拟器。队列中保存要模拟的事件，每个事件都有一个发生时间作为其关键字。

涉及算法

点击查看实现

• 堆排序

习题答案

思考题

• 6-43 Young氏矩阵

留言與分享

5. 概率分析和随机算法

当算法的时间和输入的数据有关时，往往我们需要使用概率分析得到算法运行时间的期望值（平均值）。
雇用问题这种答案不唯一的问题，也需要概率分析来分析算法的期望值，从而评估算法的有效性。

随机算法也有很广的应用，比如随机快速排序可以避免特定输入（已排序的队列或逆序列）时运行时间较长的情况。

留言與分享

4. 分治策略

本着涉及更多的分治法相关的算法，以及分治法运行时间的分析方法。

递归式

递归式可以很自然的刻画分支算法的运行时间。
递归式通过更小的输入上的函数值来藐视一个函数。
下图为归并排序的递归式：

$T(n)=\left\{ \begin{aligned} & \Theta(1) & if \quad n=1, \\ & 2T(n/2) + \Theta(n) & if \quad n>1, \end{aligned} \right.$

求解递归式的方法

• 代入法
  猜测一个界，然后用数学归纳法证明这个界的正确性
• 递归树法
  将递归式转换为一棵树，其结点表示不同层次的递归调用产生的代价。然后采用边界和技术来求解递归式。
• 主方法 可求解形式如 $T(n) = aT(n/b) + f(n)$的递归式的界

涉及算法

点击查看实现

• 最大子数组
• 矩阵乘法

练习

4.1-1

1

返回最大的一个数组成的数组

4.1-2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

FIND-MAXIMUM-SUBARRAY(A, n)
    low = 1
    high = 1
    sum = A[1]
    for i = 1 to n
        max_sum = A[i]
        tmp_sum = A[i]
        for j = i+1 to n
            tmp_sum += A[j]
            if tmp_sum > max_sum
                max_sum = tmp_sum
                tmp_low = i
                tmp_high = j
        if max_sum > sum
            sum = max_sum
            low = tmp_low
            high = tmp_high
    return (low, high, sum)

4.1-4

1

在比较left-sum, right-sum, cross-sum时，增加对0的比较，当0最大时，返回空数组

留言與分享