关于堆排序，已经研究了整整一个星期，不论是从网络论坛CSDN或者图书馆书籍中，都获益匪浅，但是知识内容都是差不多的，如何理解是自己的。这里我就写一下自堆排序的认识。
首先要弄清楚的观点是：
1、堆是一种数据结构
通常来说，一种数据结构所必备的操作有三个：初始化，插入数据，删除数据。堆也不例外。因此一旦我们写出了数据结构的基本操作，我们可以将其封装起来，用于其它的地方。比如可以用堆这种数据结构来进行其它的排序操作的实现。上升只看父节点，下降只看儿子。
2、本文中堆的存储是基于顺序数组的
因为数组的实现可以是链式或者顺序，这里实现的时候是一般情况，就是基于顺序数组的，使用顺序数组来存储堆的内容。
其中会用到的一个交换两个元素的小函数：
void exchange(int *a,int *b)
{
int temp=*a;
*a=*b;
*b=temp;
}
数据结构中的：
插入方法：
我们每次思考插入方法的时候，堆中的数据都是从数组的最后一个元素插入的。因此每次在插入一个元素以后，这个数组不再满足一个堆的条件，因此要恢复堆，基本思想就是将插入的值a[i]与他的父亲比较，再决定是否交换两者的值，一直循环，直到堆顶，直观上来看，就是新插入的元素，由堆底像堆顶上升的过程：
//堆的插入操作
void MinHeapFixUp(int a[],int i)//在结点位子插入，然后上升
{
int j;
j=(i-1)/2;
while(j>=0&&i!=0)
{
if (a[j]<a[i]) break;
exchange(&a[i],&a[j]);
i=j;
j=(i-1)/2;
}
}
void MinHeapAddNumber(int a[],int n,int nNum)//每次加入都是从数组末尾加入进去
{
a[n]=nNum;
MinHeapFixUp(a,n);
}
删除方法：
按照堆的定义，堆中每次都只能删除第0个数据。因此为了便于恢复堆，实际的操作是将最后一个数据的数据的值赋值给根的结点，然后再从根的结点开始进行一次从上向下的调整。调整时现在左右儿子中找最小的，如果父亲结点比这个最小的还要小，说明不需要调整。反之，交换两者，继续考虑其父亲。其过程相当于，从根结点将一根数据下沉的过程。
/堆删除操作:每次都删除第i个数据，然后用最后一个数据来填充删除的位子，然后恢复成最小堆
//参数中i表示从节点i开始调整，就是说i的父亲以上都已经调整完毕,n代表里面的结点总数
void MinHeapFixdown(int a[],int i,int n)
{
int left=2*i+1;
int right=left+1;
int small=left;
while(left<n)//父节点比儿子的两个结点还要小，就停止循环
{
//找出左右孩子最大的
if(right<n)
{
if (a[left]<=a[right])
{
small=left;
}
else small=right;
if (a[small]<a[i])
{
exchange(&a[small],&a[i]);
}
else break;
}
else
{
small=left;
if (a[small]<a[i])
{
exchange(&a[small],&a[i]);
}
else break;
}
i=small;
left=2*i+1;
right=left+1;
}
}
void MinHeapDeleteNumber(int a[],int n)
{
exchange(&a[0],&a[n-1]);
MinHeapFixdown(a,0,n-1);
}
初始化：
初始化有两种产生最小堆的方法：一个是利用Fixdown，另外一个是利用Fixup；
void MakeMinHeap1(int a[], int n)
{
for (int i = n/2-1; i >= 0; i--)
MinHeapFixdown(a, i, n);
}
void MakeMinHeap2(int a[],int n)
{
for (int i=0;i<n;i++)
{
MinHeapFixUp(a,i);
}
}
最后：利用堆这种数据结构实现堆排序：
void MinheapsortTodescendarray(int a[], int n)
{
for (int i = n; i >=1 ; i--)
{
MinHeapDeleteNumber(a,i);
}
}
void main()
{
int arr[]={0,1,5,4,2,7,6,8};
//MakeMinHeap1(arr,8);
MinheapsortTodescendarray(arr,8);
for (int i=0;i<8;i++)
{
printf("%d ",arr[i]);
}
printf("
");
MakeMinHeap1(arr,8);
for (int i=0;i<8;i++)
{
printf("%d ",arr[i]);
}
printf("
");
MakeMinHeap2(arr,8);
for (int i=0;i<8;i++)
{
printf("%d ",arr[i]);
}
printf("
");
}