《基本算法和结构》之堆排序。堆，一种很典型数据结构，可用于排序和优先队列，或实现一些垃圾回收机制等。
堆排序 Heap sort
算法
堆排序 heap sort，指的是利用数据结构堆完成排序，排序使用的是最大二叉堆 max heap。
最大二叉堆是一棵完全二叉树，满足如下特征：
从左至右填充。
根节点为最大元素。
除根节点外，所有节点都要小于等于其父节点。
如图所示：
堆不是线性结构，但通常可以用数组进行表示，因为堆每个节点的索引很容易计算，给定一个节点索引 i，很容易计算出其父节点、左子节点和右子节点的索引：
父节点：
i / 2
或i >> 1左子节点：
i * 2
或i << 1右子节点：
i * 2 + 1
或i << 1 + 1
以上最大堆，可以使用下面的数组表示：
堆排序最关键的步骤是将数组序列最大堆化，思路是提供功能给定一个节点索引，可以将该索引对应的节点及其子节点维护为满足最大堆的性质，该操作称为最大堆化，是一个递归的操作，思路是：
假定 i 的左右子节点都满足最大堆特性。存在该假定的理由是我们是从叶子节点向根节点进行最大堆化的。
找出 i 和 其左右节点三个值中的最大值索引 largest。
若largest == i，说明 i 已经满足最大堆性质，任务完成。
若 largest != i，说明 i 不满足，交换 largest 和 i 的值，然后，递归地对 largest 继续做最大堆化操作。
维护好堆结构后，堆排序就可以基于以上的最大堆完成排序，具体过程是：
先将待排序序列构建为最大堆。此时根元素为最大元素。
再将根元素与最后的元素置换，此时最大元素位于最后元素上，最大元素排序完毕。
之后将除了最后一个元素的前面元素再次构建为最大堆，然后将最大根元素与倒数第二个元素交换。
重复以上步骤，依次将最大元素置换的对应的位置上，直到未排序元素只有1个，排序结束。
编码
go
1// 堆排序
2func HeapSort(data []int) {
3 // 构建最大堆
4 BuildMaxHeap(data)
5 // 控制满足最大堆元素个数
6 size := len(data)
7 // 依次获取最大元素，放在序列后
8 for i:=len(data)-1; i>=1; i-- {
9 // 交换根节点和当前元素
10 data[i], data[0] = data[0], data[i]
11 // 最大堆尺寸-1，后边元素已经排序完成
12 size -= 1
13 // 交换元素后，重新最大堆化
14 maxHeapfy(data, 0, size)
15 }
16}
17// 构建最大堆
18func BuildMaxHeap(data []int) {
19 // 从第一个具有子节点的节点开始构建
20 l := len(data)
21 for i:=l/2; i>=0; i-- {
22 // 维护 i 节点最大堆
23 maxHeapfy(data, i, l)
24 }
25}
26
27// 维护 i 节点的最大堆性质
28// size 是最后一个对元素索引
29func maxHeapfy(data []int, i, size int) {
30 // 确定左右子节点索引
31 l, r := i<<1, i<<1 + 1
32 // 判断最大值位于哪个索引
33 largest := i
34 if l < size && data[l] > data[largest] {
35 largest = l
36 }
37 if r < size && data[r] > data[largest] {
38 largest = r
39 }
40 // 若索引 i 不是最大值
41 if i != largest {
42 // 则交换 i 和 largest 索引元素
43 data[i], data[largest] = data[largest], data[i]
44 // 递归维护 largest 元素的最大堆性质
45 maxHeapfy(data, largest, size)
46 }
47}
48
49// 测试通过
50data := []int{5, 3, 8, 1, 2, 7, 4, 0, 9, 6}
51HeapSort(data)
52fmt.Println(data) // [0 1 2 3 4 5 6 7 8 9]
Python
JavaScript
PHP
分析
堆排序的时间复杂度为 O(nlgn)，同样是原址排序，不需要额外的存储空间。除了最大堆，还有最小堆，最小堆通常用来构建优先队列。
