介绍
堆排序是指利用堆这种数据结构所设计的一种排序算法，堆是一个近似完全二叉树的数据结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
- 二叉树：二叉树是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。
- 满二叉树：二叉树的第 i 层至多拥有 2^(i-1) 个节点；深度为 k 的二叉树至多总共有 2^(k+1) - 1 个节点，而总计拥有节点数匹配的，称为满二叉树。
- 完全二叉树：深度为 k 有 n 个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k 的满二叉树，序号为 1 到 n 的节点一对一对应时，称为完全二叉树
通常堆是通过一维数组来实现存储的。在数组起始位置为0的情形中：
- 父节点i的左子节点在位置(2i+1) ;
- 父节点i的右子节点在位置(2i+2);
- 子节点i的父节点在位置floor((i-1)/2) ;
步骤
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
- 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
- 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
- 堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
演示
Sorting_heapsort_anim.gif
复杂度
最坏时间复杂度：O(nlog n)
最优时间复杂度：O(nlog n)
平均时间复杂度：O(n*log n)
最坏空间复杂度：O(n)，需要辅助空间O(1)
python
def heap_sort(lst):
def sift_down(start, end):
"""最大堆调整"""
root = start
while True:
child = root * 2 + 1 # 左孩子
if child > end:
break
if child + 1 <= end and lst[child] < lst[child + 1]: # 在左右孩子中找最大的
child += 1
if lst[root] < lst[child]: # 把较大的子结点往上移动,替换它的父结点
lst[root], lst[child] = lst[child], lst[root]
root = child
else: # 父子节点顺序正常 直接过
break
# 创建最大堆
for start in range(len(lst) // 2 - 1, -1, -1):
# 从第一个非叶子结点从下至上，从右至左调整结构
sift_down(start, len(lst) - 1)
# 堆排序
for end in range(len(lst) - 1, 0, -1):
lst[0], lst[end] = lst[end], lst[0] # 将堆顶元素与末尾元素进行交换
sift_down(0, end - 1) # 重新调整子节点的顺序 从顶开始调整
return lst
l = [9, 2, 1, 7, 6, 8, 5, 3, 4]
print(heap_sort(l))
java
private static int leftChild(int i) {
return 2 * i + 1;
}
private static <AnyType extends Comparable<? super AnyType>> void swap(AnyType[] b, int j, int i) {
AnyType tmp;
tmp = b[i];
b[i] = b[j];
b[j] = tmp;
}
private static <AnyType extends Comparable<? super AnyType>> void percDown(AnyType[] a, int i, int n) {
int child;
AnyType tmp;
for(tmp = a[i]; leftChild(i) < n; i = child) {
child= leftChild(i);
if(child != n - 1 && a[child].compareTo(a[child + 1]) < 0)
child++;
if(tmp.compareTo(a[child]) < 0)
a[i] = a[child];
else
break;
}
a[i] = tmp;
}
public static <AnyType extends Comparable<? super AnyType>> void heapsort(AnyType[] a) {
for(int i = a.length / 2 - 1; i >= 0; i--)
percDown(a, i, a.length);
for(int i = a.length - 1; i > 0; i--) {
swap(a, 0, i);
percDown(a, 0, i);
}
}
