简介
堆排序（英语：Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
堆的操作
在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话堆中的最小值位于根节点）。堆中定义以下几种操作：
最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算。
实现示例
C语言
#include
#include
void 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 <= end) //若子节点指标在范围内才做比较
{
if (son + 1 <= end && arr[son] < arr[son + 1])
//先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
return;
else //否则交换父子内容再继续子节点和孙节点比较
{
swap(&arr[dad]， &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[]， int len)
{
int i;
//初始化，i从最後一个父节点开始调整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr， i， len - 1);
//先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
for (i = len - 1; i > 0; i--)
{
swap(&arr[0]， &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);
int i;
for (i = 0; i < len; i++)
printf("%d "， arr[i]);
printf("n");
return 0;
}
C++
#include
#include
using namespace std;
void max_heapify(int arr[]， int start， int end)
{
//建立父节点指标和子节点指标
int dad = start;
int son = dad * 2 + 1;
while (son <= end) //若子节点指标在范围内才做比较
{
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的
son++;
if (arr[dad] > 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 >= 0; i--)
max_heapify(arr， i， len - 1);
//先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕
for (int i = len - 1; i > 0; i--)
{
swap(arr[0]， arr[i]);
max_heapify(arr， 0， i - 1);
}
}
void 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 < len; i++)
cout << arr[i] << ' ';
cout << endl;
system("pause");
}
Java语言
/**
* 选择排序-堆排序
* @param array 待排序数组
* @return 已排序数组
*/
public static int[] heapSort(int[] array) {
//这里元素的索引是从0开始的，所以最后一个非叶子结点array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array， i， array.length); //调整堆
}
// 上述逻辑，建堆结束
// 下面，开始排序逻辑
for (int j = array.length - 1; j > 0; j--) {
// 元素交换，作用是去掉大顶堆
// 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
swap(array， 0， j);
// 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
// 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
// 而这里，实质上是自上而下，自左向右进行调整的
adjustHeap(array， 0， j);
}
return array;
}
/**
* 整个堆排序最关键的地方
* @param array 待组堆
* @param i 起始结点
* @param length 堆的长度
*/
public static void adjustHeap(int[] array， int i， int length) {
// 先把当前元素取出来，因为当前元素可能要一直移动
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1为左子树i的左子树(因为i是从0开始的)，2*k+1为k的左子树
// 让k先指向子节点中最大的节点
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子树，并且右子树大于左子树
k++;
}
//如果发现结点(左右子结点)大于根结点，则进行值的交换
if (array[k] > temp) {
swap(array， i， k);
// 如果子节点更换了，那么，以子节点为根的子树会受到影响，所以，循环对子节点所在的树继续进行判断
i = k;
} else { //不用交换，直接终止循环
break;
}
}
}
/**
* 交换元素
* @param arr
* @param a 元素的下标
* @param b 元素的下标
*/
public static void swap(int[] arr， int a， int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
Python语言
def big_endian(arr，start，end):
root=start
child=root*2+1 #左孩子
while child<=end:
#孩子比最后一个节点还大，也就意味着最后一个叶子节点了，就得跳出去一次循环，已经调整完毕
if child+1<=end and arr[child]
#为了始终让其跟子元素的较大值比较，如果右边大就左换右，左边大的话就默认
child+=1
if arr[root]
#父节点小于子节点直接交换位置，同时坐标也得换，这样下次循环可以准确判断：是否为最底层，
#是不是调整完毕
arr[root]，arr[child]=arr[child]，arr[root]
root=child
child=root*2+1
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[0]，arr[end]=arr[end]，arr[0] #顶部尾部互换位置
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()
PHP语言
function hsort(array &$arr， $len){
$idx = $len - 1;
//创建堆操作，并使得堆有序
for($k=floor($len/2); $k>=0; $k--){
sink($arr， $k， $idx);
}
//排序操作
while($idx>0){
//获取最大值操作
list($arr[0]， $arr[$idx]) = [$arr[$idx]， $arr[0]];
$idx--;
//堆调整下沉
sink($arr， 0， $idx);
}
}
//堆调整下沉，小数字下沉
function sink(array &$arr， $low， $high){
//从$low开始找子节点
while($low*2+1<=$high){
//获取low的直接左子节点
$j = $low*2+1;
//判断$low位置节点子节点中的较大子节点
if($j<$high && $arr[$j]<$arr[$j+1]){
$j++;
}
if($arr[$low]>$arr[$j]){
break;
}
//交换low节点和子节点的值
list($arr[$low]， $arr[$j]) = [$arr[$j]， $arr[$low]];
//继续排查下沉后子节点是否需要进行下沉操作
$low = $j;
}
}
$a = [4，3，6，7，5，1，9，0，2];
hsort($a， count($a));
print_r($a);
