堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆的操作
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
实现示例
C语言
#include \u003cstdio.h\u003e#include \u003cstdlib.h\u003evoid swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp;}void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son \u003c= end) { //若子节点指标在范围内才做比较 if (son + 1 \u003c= end \u0026\u0026 arr[son] \u003c arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; if (arr[dad] \u003e arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数 return; else { //否则交换父子内容再继续子节点和孙节点比较 swap(\u0026arr[dad], \u0026arr[son]); dad = son; son = dad * 2 + 1; } }}void heap_sort(int arr[], int len) { int i; //初始化，i从最後一个父节点开始调整 for (i = len / 2 - 1; i \u003e= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕 for (i = len - 1; i \u003e 0; i--) { swap(\u0026arr, \u0026arr[i]); max_heapify(arr, 0, i - 1); }}int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); int i; for (i = 0; i \u003c len; i++) printf("%d ", arr[i]); printf("\n"); return 0;}
C++
#include \u003ciostream\u003e#include \u003calgorithm\u003eusing namespace std;void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son \u003c= end) { //若子节点指标在范围内才做比较 if (son + 1 \u003c= end \u0026\u0026 arr[son] \u003c arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; if (arr[dad] \u003e arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数 return; else { //否则交换父子内容再继续子节点和孙节点比较 swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } }}void heap_sort(int arr[], int len) { //初始化，i从最後一个父节点开始调整 for (int i = len / 2 - 1; i \u003e= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕 for (int i = len - 1; i \u003e 0; i--) { swap(arr, arr[i]); max_heapify(arr, 0, i - 1); }}int main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i \u003c len; i++) cout \u003c\u003c arr[i] \u003c\u003c ' '; cout \u003c\u003c endl; return 0;}
Python语言
def big_endian(arr, start, end): root = start while True: child = root * 2 + 1 # 左孩子 if child \u003e end: # 孩子比最后一个节点还大 也就意味着最后一个叶子节点了 就得跳出去一次循环已经调整完毕 break if child + 1 \u003c= end and arr[child] \u003c arr[child + 1]: # 为了始终让其跟子元素的较大值比较 如果右边大就左换右，左边大的话就默认 child += 1 if arr[root] \u003c arr[child]: # 父节点小于子节点直接换位置 同时坐标也得换这样下次循环可以准确判断是否为最底层是不是调整完毕 arr[root], arr[child] = arr[child], arr[root] root = child else: # 父子节点顺序正常 直接过 break def heap_sort(arr): # 无序区大根堆排序 first = len(arr) // 2 - 1 for start in range(first, -1, -1): # 从下到上，从右到左对每个节点进调整 循环得到非叶子节点 big_endian(arr, start, len(arr) - 1) # 去调整所有的节点 for end in range(len(arr) - 1, 0, -1): arr, arr[end] = arr[end], arr # 顶部尾部互换位置 big_endian(arr, 0, end - 1) # 重新调整子节点的顺序 从顶开始调整 return arr def main(): l = [3, 1, 4, 9, 6, 7, 5, 8, 2, 10] print(heap_sort(l)) # 原地排序 if __name__ == "__main__": main()