算法课

这一次归纳一下堆排序
堆排序是一种优先级队列的实现，近似完全二叉树
一个优先级队列可以有如下4种操作：

Insert(S, x): 插入元素x到S集合中
Max(S): 返回S中最大的元素
Extract_max(S): 和Max操作相似，但同时从S中去掉那个最大的元素，相当于pop
Increase_key(S, x, k): 将元素x的key值设为k

堆的实现

在敲代码时，一般用一个数组就可以看成一个堆。
有如下特性：

root of tree: 第一个元素
parent(i): 下标为i的元素的父节点为i / 2(PS: 奇数向下取整)
left_child(i): 下标为i的元素的左子节点为2i
right_child(i): 下标为i的元素的右子节点为2i+1
实现一遍变可以很容易理解

最大堆的特性

一个节点的key 大于等于其children的key

堆操作

max_heapify: 对于一个root来说，其左子树和右子树都已经是最大堆了，而本身却不一定大于左子树和右子树的根，需要将其最大堆化

max_heapify(A, i)
if max(A[i], A[2i], A[2i+1]) != A[i]
  Exchange bigger Child(A[2i], A[2i+1])
  Until no more call

很容易知道max_heapify的时间花费为：O(lgn)

Build_max_heap(A):
  for i = n / 2 down to 1
    do max_heapify(A, i)

乍看之下，很容易以为Build_max_heap(A)的时间花费为：nlgn
然而仔细思考，一般来说是在倒数第二层开始max_heapify，而在倒数第二层进行这个操作的时候，是只花了O(1)的时间的。
所以倒数第L层的节点来说，耗时为O(L)时间。
设总数为n，n/4的节点在倒数第一层，n/8的节点在倒数第二层...
因此Total amount of work:
$n/4O(1c) + n/8O(2c)+ n/16O(3c) + 1O(lgnC)$
设 $n/4=2^k$
$C2^k(\frac{1}{2^0}+\frac{2}{2^1}+\frac{3}{2^2} + ... + \frac{k+1}{2^k})$
由极限思想知括号内的多项式的上界为一个常数
因此Total amount为 $O(C2^k)$ 即 $\Theta(n)$