堆排序（一个迭代的过程）
一、二叉堆的定义
二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：
1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。
当父结点的key总是大于或等于任何一个子节点的key时为最大堆。
当父结点的key总是小于或等于任何一个子节点的key时为最小堆。下图展示一个最小堆：

由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。

二、什么是堆排序（堆排序的过程描述）
N个元素建立二叉堆，将原来无序的序列（数组）插入到二叉树（线性二叉树），在插入的过程中不断调整二叉树为最小堆或者最大堆。
在全部插入完毕之后，此时并未排序完毕，但是已经建立起最小堆或者最大堆，堆中每一个根节点都是当前树或子树中的最小值或最大值，此时还需要进行进一步的调整来完成最终的排序。
简单说来，堆排序一共包含两个操作。第一步，建立最小堆或最大堆；第二步，将跟节点与最后一个叶子节点进行互换，并取出根节点，对已经打破规则的二叉堆进行新的调整，使其变成新的最小堆或者最大堆。
以上两步，反复进行，直到完成最终的排序。

三、堆排序的核心（以最小堆为例）
1.由于堆排序在进行的过程中，无论排序是否完成，根节点的key都是整个树中最小的，子树的根节点同样也是子树中key最小的。
2.打破当前二叉堆，建立新的二叉堆的过程就是取出当前节点值，并将数组中最后一个元素取代当前根节点；由于最后一个元素的值不一定是整个堆中的最小值，于是就打破了最小堆的规则，这个时候就要进行新的调整，将当前二叉树调整为新的最小堆，调整过程与前期插入时的过程一样。
那么每一次调整完毕之后，将根节点取出，就可以取得当前二叉树的最小值，整个过程完毕之后就得到一个从小到大排列的数组（该树形结构实际为数组）。
3.其中，调整的过程中核心的过程是：将当前二叉树中的最后一个元素替换到当前根的位置，比较根的左右孩子的值找出其中最小的，再与新的根节点进行比较；
eg：左孩子>右孩子，同时，根节点>右孩子，则根节点与右孩子互换；左孩子<右孩子，同时，左孩子<根节点，则根节点与左孩子交换。

for(i=len-1;i>0;i--){//堆顶元素和最后一个元素交换位置，//这样最后的一个位置保存的是最小的数，//每次循环依次将次小的数值在放进其前面一个位置，//这样得到的顺序就是从大到小int temp = arr[i];arr[i] = arr[0];arr[0] = temp;//将arr[0...i-1]重新调整为最小堆HeapAdjustDown(arr,0,i-1);}

四、建立最小堆的过程的代码

/*
arr[start+1...end]满足最大堆的定义，
将arr[start]加入到最大堆arr[start+1...end]中，
调整arr[start]的位置，使arr[start...end]也成为最大堆
注：由于数组从0开始计算序号，也就是二叉堆的根节点序号为0，
因此序号为i的左右子节点的序号分别为2i+1和2i+2
*/
void HeapAdjustDown(int *arr,int start,int end)
{int temp = arr[start];  //保存当前节点int i = 2*start+1;      //该节点的左孩子在数组中的位置序号while(i<=end){//找出左右孩子中最大的那个if(i+1<=end && arr[i+1]>arr[i])  i++;//如果符合堆的定义，则不用调整位置if(arr[i]<=temp)    break;//最大的子节点向上移动，替换掉其父节点arr[start] = arr[i];start = i;i = 2*start+1;}arr[start] = temp;
}

  下面是第二部完成调整，进行排序的代码

/*
堆排序后的顺序为从小到大
因此需要建立最大堆
*/
void Heap_Sort(int *arr,int len)
{int i;//把数组建成为最大堆//第一个非叶子节点的位置序号为len/2-1for(i=len/2-1;i>=0;i--)HeapAdjustDown(arr,i,len-1);//进行堆排序for(i=len-1;i>0;i--){//堆顶元素和最后一个元素交换位置，//这样最后的一个位置保存的是最大的数，//每次循环依次将次大的数值在放进其前面一个位置，//这样得到的顺序就是从小到大int temp = arr[i];arr[i] = arr[0];arr[0] = temp;//将arr[0...i-1]重新调整为最大堆HeapAdjustDown(arr,0,i-1);}
}

  最后的调用

int main()
{int num;printf("请输入排序的元素的个数：");scanf("%d",&num);int i;int *arr = (int *)malloc(num*sizeof(int));printf("请依次输入这%d个元素（必须为整数）：",num);for(i=0;i<num;i++)scanf("%d",arr+i);printf("堆排序后的顺序：");Heap_Sort(arr,num);for(i=0;i<num;i++)printf("%d ",arr[i]);printf("\n");free(arr);arr = 0;getchar();getchar();//如果不用getchar();//用#include<windows.h> system("pause");也行return 0;
}

堆排序的演示过程可以参考：

https://bajdcc.github.io/html/heap.html

https://www.bilibili.com/video/av12667435/?from=search&seid=2680440824139560440

其他优质讲解资源：

http://blog.csdn.net/morewindows/article/details/6709644/

http://blog.csdn.net/xiaoxiaoxuewen/article/details/7570621/

http://www.360doc.com/content/14/0804/11/1073512_399302715.shtml

http://blog.csdn.net/ns_code/article/details/20227303

https://bajdcc.github.io/html/heap.html