最小堆：所有父节点都比子节点小的完全二叉树
最大堆：所有父节点都比子节点大的完全二叉树
对于二叉树的知识这里不再赘述
操作：把最小数删除，并插入一个数
先看代码：
void siftdown(int i)
{
int t,flag=0;
while(i*2<=n&&flag==0)//t代表三个里面最小值
{
if(h[i*2]>h[i])
t=i;
else
t=i*2;
if(i*2+1<=n)
if(h[t]>h[i*2+1])
t=i*2+1;
if(t!=i)
{
swap(t,i);//交换
i=t;//赋值，继续判断
}
else //如果父节点不再大于子节点，则跳出循环
flag=1;
}
}
就相当于不断判断，直到其移动到符合父节点小于子节点的位置。
同理可以添加一个叶节点，然后向上移动，直到满足条件：
来看代码：
void shiftup(int i)
{
int t,flag=0;
if(i==1) return ;
while(i/2>=1&&flag==0)
{
if(h[i/2]>h[i])
{
t=i/2;
swap(i,t);
i=t;
}
else
flag=1;//父节点比子节点小
}
}如何创建一个最小（大）堆：
基本思想：先把一无序的数放入一个数组里面，然后进行操作。
操作方法：把非叶节点的节点都依次向下判断 ： 最后一个节点为n/2 则
void creat()
{
int i;
for(i=n/2;i>=1;i--)
{
siftdown(i);
}
}这样做的效果就是，使得最上面的节点一定为最小值，好，那么最小值找出来了，那我们就进行以下操作：
int deletemax()
{
int t;
t=h[1];
h[1]=h[n];//n is the number of array
n--;
siftdown(1)
return t;
}
for(i=1;i<=n;i++)
printf("%d ",deletemax());
这样就把n个数按从小到大顺序输出。
这样，我们就实现了堆排序。
总结一下：堆排序的基本思想：利用堆的特点，依次找出最小（大）值，实现排序。
所有代码：
#include<stdio.h>
#include<string.h>
#include<math.h>
int h[1000],n;
void swap(int x,int y);
void siftdown(int i);
void siftup(int i);
void creat();
int deletemax();
void print();
int main()
{
int i,num;
printf("please input the number of array:");
scanf("%d",&num);
for(i=1;i<=num;i++)
scanf("%d",&h[i]);
n=num;
creat();
//print();
for(i=1;i<=num;i++)
printf("%d ",deletemax());
return 0;
}
void swap(int x,int y)
{
int t;
t=h[x];
h[x]=h[y];
h[y]=t;
}
void siftdown(int i)
{
int t,flag=0;
while(i*2<=n&&flag==0)//t代表三个里面最小值
{
if(h[i*2]>h[i])
t=i;
else
t=i*2;
if(i*2+1<=n)
if(h[t]>h[i*2+1])
t=i*2+1;
if(t!=i)
{
swap(t,i);//交换
i=t;//赋值，继续判断
}
else //如果父节点不再大于子节点，则跳出循环
flag=1;
}
}
void shiftup(int i)
{
int t,flag=0;
if(i==1) return ;
while(i/2>=1&&flag==0)
{
if(h[i/2]>h[i])
{
t=i/2;
swap(i,t);
i=t;
}
else
flag=1;//父节点比子节点小
}
}
void creat()
{
int i;
for(i=n/2;i>=1;i--)
{
siftdown(i);
//print();
}
}
int deletemax()
{
int t;
t=h[1];
h[1]=h[n];
n--;
siftdown(1);
return t;
}
void print()
{
int i;
for(i=1;i<=n;i++)
printf("%d ",h[i]);
printf("\n");
}