最大堆 排序

卸载最前面，下面的所有讨论都是基于二叉堆

一:什么是堆：
堆是一个数组结构，可以看着为一颗完全二叉树，把这颗完全二叉树按层从上到下，每层从左至右编序号，每个序号所对应的元素即为数组中该序号的元素；该树出最后一层以外每一层都排满，最后一层从左至右，先左孩子再右孩子排列，如果有父节点没有排满孩子（无孩子或无右孩子），只可能是右边的父节点未排满孩子。
因此该结构有如下结构：
如果节点i，则它的左孩子为2*I,右孩子为2*i+1;原因：节点i所对应的深度为h=log2(i);所以左孩子为2^log2(i)+2*(i-i/2)=2i;
二：堆排序过程
先构建堆—》把最后一个节点和第一个节点互换—》调整堆—》第一个节点与倒数第二个节点互换，依次进行:
三：代码
#include <stdio.h>
#include <math.h>
/*
假设i的左孩子与右孩子已经是一个最大堆，现在要把i放入到堆中，如果i比左右孩子都大直接放入，如果i比左孩子或者右孩子小，则与该孩子互换，交换以后再调整该孩子所在子树，一直调整到合适位置为止
*/
void heapify(int *pArray, int i, int iHeapSize)
{
int iLargest = i;
int iLeft = 2*i, iRight = 2*i+1;
int tmp;
if(iLeft < iHeapSize && *(pArray+i) < *(pArray+iLeft))
{
if(*(pArray+i) < *(pArray+iLeft))
{
iLargest = iLeft;
}
else
{
iLargest = i;
}
}
if(iRight < iHeapSize && *(pArray + iRight) > *(pArray + iLargest))
{
iLargest = iRight;
}

if(i != iLargest)
{
tmp =  *(pArray + iLargest);
*(pArray + iLargest) = *(pArray+i);
*(pArray+i) = tmp;
  heapify(pArray, iLargest, iHeapSize);
}
else
{
return;
}
}
/*
因为n/2+1~n都为叶子节点；
最后一层深度h = log2(n);倒数第二层最后一个节点为：2^(log2(n)-1)=n/2
*/
void buid_heap(int *pArray, int size)
{
for(int i = size/2-1; i >= 0;  i--)
{
heapify(pArray, i, size);
}
}

void heap_sort(int *pArray, int size)
{
int tmp;
int i;
buid_heap(pArray, size);
for(i = 0; i < size; ++i)
{
tmp = *(pArray);
*(pArray) = *(pArray + (size-1-i));
*(pArray + (size-1-i)) = tmp;
heapify(pArray, 0, size - i-1);
}
}