c++堆排序图文介绍堆排序的理解实例源码，其实堆排序是利用堆的性质进行的选择排序方式。下面我们先来了解一下什么是堆。
1.堆，就是一棵完全二叉树，它的任意非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
也就是说所有的非叶节点的关键字不大于或是不小于左右孩子节点的关键字。堆可以分作大顶堆以及小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]的堆叫做大顶堆，条件为Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]的堆叫做小顶堆。大顶堆的堆顶的关键字是所有关键字中最大的，小顶堆堆顶关键字为任何关键字中最小的。
2.堆排序的思想解析
采用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)的特性，每次从无序中选择最大记录(最小记录)变得简单。
它的基本思想为(大顶堆)：
1)把初始的排序关键字序列(R1,R2….Rn)构建成大顶堆，这个堆是初始的无序区；
2)把堆顶元素R[1]以及最后一个元素R[n]交换，这时候就可以获取到新的无序区(R1,R2,……Rn-1)以及新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3)交换后新堆顶R[1]也许会违反堆的性质，所以对当前无序区(R1,R2,……Rn-1)调整为新堆，再把R[1]以及无序区最后的元素交换，取得新的无序区(R1,R2….Rn-2)以及新的有序区(Rn-1,Rn)。反复地执行该过程一直到有序区的元素个数为n-1，那么整个排序过程完成。
操作过程如下：
1)初始化堆：将R[1..n]构造为堆；
2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。
对于堆排序，最重要的两个操作就是构造初始堆以及调整堆，事实上构造初始堆也是调整堆的过程，而构造初始堆是对所有的非叶节点都进行调整。
举例介绍：
一个整形数组a[]={16,7,3,20,17,8}，对该数组进行堆排序。
先依据该数组元素构建一个完全二叉树，获得：
接着构造初始堆，从最末尾一个非叶节点开始调整，调整过程如下：
20与16交换后使得16不满足堆的性质，所以要重新调整
得到了初始堆。每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。
此时3位于堆顶不满堆的性质，则需调整继续调整
/*堆排序(大顶堆) 2011.9.14*/
#include <iostream>
#include<algorithm>
using namespace std;
void HeapAdjust(int *a,int i,int size) //调整堆
{
int lchild=2*i; //i的左孩子节点序号
int rchild=2*i+1; //i的右孩子节点序号
int max=i; //临时变量
if(i<=size/2) //如果i是叶节点就不用进行调整
{
if(lchild<=size&&a[lchild]>a[max])
{
max=lchild;
}
if(rchild<=size&&a[rchild]>a[max])
{
max=rchild;
}
if(max!=i)
{
swap(a[i],a[max]);
HeapAdjust(a,max,size); //避免调整之后以max为父节点的子树不是堆
}
}
}
void BuildHeap(int *a,int size) //建立堆
{
int i;
for(i=size/2;i>=1;i--) //非叶节点最大序号值为size/2
{
HeapAdjust(a,i,size);
}
}
void HeapSort(int *a,int size) //堆排序
{
int i;
BuildHeap(a,size);
for(i=size;i>=1;i--)
{
//cout<<a[1]<<" ";
swap(a[1],a[i]); //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面
//BuildHeap(a,i-1); //将余下元素重新建立为大顶堆
HeapAdjust(a,1,i-1); //重新调整堆顶节点成为大顶堆
}
}
int main(int argc, char *argv[])
{
//int a[]={0,16,20,3,11,17,8};
int a[100];
int size;
while(scanf("%d",&size)==1&&size>0)
{
int i;
for(i=1;i<=size;i++)
cin>>a[i];
HeapSort(a,size);
for(i=1;i<=size;i++)
cout<<a[i]<<"";
cout<<endl;
}
return 0;
}