堆排序实战：理解再实现

Contents

1. 1. 关于堆
2. 2. 算法基本思想
3. 3. Max-Heapify
4. 4. Build-Max-Heap
5. 5. Heap-Sort
6. 6. 输出与比较

　　堆排序我已经遗忘得差不多了，只记得有这么一种方式，且时间复杂度为n*log(n)。下面要做的是根据其算法描述来自行实现，作为一种练习。

关于堆

　　看了一下wiki的前两段，大致知道了此处堆实质是二叉树，常用一维数组来表示，有一个很重要的规律，对于以0开头的数组：左右子节点的序号分别为2*i+1, 2*i+2。

　　作为一个喜欢用理解帮助记忆的人，想弄明白为何如此。

1. 对每个节点，i = 前（上层及左边）节点数，这是显然的。
2. 本层的节点数 = 所有上层节点数之和 + 1。（等比数列）
3. 所以对每层最左节点，2*i为本层最右节点，2*i+1, 2*i+2是下层第一二节点，自然是i的子节点
4. 自i每右移1,2×i移2,依然是其左右子结点。

　　以上是堆的父子节点序号对应规律，是进行节点操作的基础。

算法基本思想

　　堆排序的算法过程不是很好理解，因为牵涉到不少术语，我看了一堆网文博客之后，依然一知半解，尝试实现时总是遇到问题，最后看了《算法导论》之后，才算是明白了。

1. max-heapify最大堆化，这里有一个前提：左右子树已经是最大堆了
2. build-max-heap建立最大堆，将一个无序输入转化为最大堆，这里有反复调用1
3. head-sort 最大堆的首尾元素对换，然后对[0,len-1]的部分执行1
4. 直到数组长为1

Max-Heapify

　　现在可以来实现1了，具体的思路是：

1. 将root与左右子节点的最大者互换（如果root已是最大，直接结束）
2. 被替换的节点成为root，继续与其子节点替换，直到无子节点。

　　用代码实现：

def siftDown(a, s, e):
    root = s
    while 2 * root + 1 <= e:
        c = 2 * root + 1
        if a[c] <= a[c + 1]:
            c += 1
        if a[root] < a[c]:
            a[root], a[c] = a[c], a[root]
        root = c

Build-Max-Heap

1. 对于没有后代的节点，视为最大堆。
2. 从最后一个有子节点的点开始，往前执行1，这样能够保证，每个被处理的节点的子树都是最大堆（1的条件）
3. 一直执行到root，这样整个堆都是最大堆

# build max heap
end = len(a) - 1
for i in range((end - 1) / 2, -1, -1):
    siftDown(a, i, end)

Heap-Sort

　　首尾互换，最大值已在数组尾，对a[0,end-1]部分执行1,直到到达头部。

while end >= 0:
    a[0], a[end] = a[end], a[0]
    end -= 1
    siftDown(a, 0, end)
print a

输出与比较

　　对20000个随机整数进行快速，堆和冒泡排序，其时间分别为：

0.0850009918213
0.141738891602
36.0431509018

　　可见堆排序和快速排序同为n*log(n)时间性能，稍劣于快速排序，较n^2的冒泡排序快2个数量级。