堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出(最大堆调整的递归运算)，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作：
最大堆调整（Max-Heapify):
将堆的末端子节点作调整，使得子节点永远小于父节点
创建最大堆（Build-Max-Heap):
将堆所有数据重新排序，使其成为最大堆
堆排序（Heap-Sort):
移除位在第一个数据的根节点，并做最大堆调整的递归运算
继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变
相应的，几个计算公式也要作出相应调整：
Parent(i) = floor((i-1)/2)，i 的父节点下标
Left(i) = 2i + 1，i 的左子节点下标
Right(i) = 2(i + 1)，i 的右子节点下标
最大堆调整（MAX‐HEAPIFY）的作用是保持最大堆的性质，是创建最大堆的核心子程序，作用过程如图所示：
创建最大堆（Build-Max-Heap）的作用是将一个数组改造成一个最大堆，接受数组和堆大小两个参数，Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组，建立最大堆。因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质，所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。如果最大堆的数量元素是 n，那么 Build-Max-Heap 从 Parent(n) 开始，往上依次调用 Max-Heapify。流程如下
堆排序（Heap-Sort）是堆排序的接口算法，Heap-Sort先调用Build-Max-Heap将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，最后重新调用Max-Heapify保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。整个流程如下：
C语言实现:
#include <stdio.h>
#include <stdlib.h>
void swap(int *arr,int i, int k)
{
int temp = arr[i];
arr[i] = arr[k];
arr[k] = 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, son);
printf("dad=%d--son=%d\n",dad,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, i);
max_heapify(arr, 0, i - 1);
}
}
int main(int argc, char const *argv[])
{
int arr[] = {5,3,8,1,6};
int len = sizeof(arr) / sizeof(int);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
步骤详解:
下标0 1 2 3 4
Array={5,3,8,1,6};
Len=5
i=5/2 -1 =1 为最后一个元素的父节点的下标值
Max_heapity(arr,i,len-1)
i=1 len-1=4 end=4
1 > 6 son=4
dad=4
son=4*2+1=9
9>4 while 第一次结束
i=0
Max_heapity(arr,0,4)
dad=0 ; end=4 son=1
1 < 4
6< 8
son=2
dad=2
son=2*2 +1 =5
5<end=4 while 第二次结束
i=-1 i<0 第一个for循环结束
第二个for循环开始
len=5
i=len-1=4
max_heapity(arr,0,3)
dad=0 son=1 end=3
son=3 dad=1
while 第三次结束
i=3 len=5
swap(arr,0,3)
max_heapify(arr,0,2);
dad=0; son=1;end=2
3 < 5
son=2
dad=2
son=2*2+1=5
while 第四次结束
i=2 len=5
max_heapity(arr,0,1)
dad=0; son=1 end=1
i=1 len=5
max_heapity(arr,0,0)
dad=0; son =1
1<0 while跳出
i=0时 第二个for循序结束
最终结果: 13 5 6 8
