堆是一个数组，可以看作是一个近似于完全二叉树，树每个接点对应数组中的每个元素，除了最底层外，该树完全是满的，且在数组中是从左到右填充的，表示堆的数组通常有两个属性，一个是length 表示数组A的长度，一个是heap_size数组A实际有效长度。也就是说在在A中都可以存储元素，但是实际存入的有效元素只是
，heap_size满足
，树的根节点是使A[1]，所以指定树的根节点下标我们就很容易计算出左右子节点下标。计算节点下标方式如下：
以上三个计算坐标的函数你可以通过定义宏来实现。
在二叉堆中，有最大堆与最小堆分别，最大堆：最大的节点值永远都在父节点上，其他节点的值最大只能与父节点的值相等，即始终要满足,同样在任意子树中都要满足以上条件。同理最小堆：最小的节点值永远都在父节点上，其他节点的值最小只能与父节点的值相等，即要满足
，二者刚好相反。
在这里采用的是最大二叉堆实现排序，其过程如下：1.初始化建树；2.调整二叉树（堆），保证整体满足最大堆的要求；3.在遍历根节点，并且依次从右向左填入根节点，再执行第2，3两个步骤，直到结束，跳出循环，排序就完成了。
以下便是堆排序的源程序：
#include <stdio.h>
//define index of left,right
#define index_left(i) 2*i+1
#define index_right(i) 2*i+2
/*****************************************************
*
* function max_heapify();
*
* args
* A inttype array of a heap elements
* i inttype index of A
* heap_szie the real length of input elements of A
* but heap_size=length-1,because of index
* from 0 to n-1
*
* ***************************************************/
void max_heapify(int A[],int i,int heap_size){
int l,r,largest,temp;
//calculate index of left and right child
l=index_left(i);
r=index_right(i);
//index l,r compare with the heap_size of A
if((l<=heap_size)&&(A[l]>A[i]))
largest=l;
else
largest=i;
// right child
if((r<=heap_size)&&(A[r]>A[largest]))
largest=r;
if(largest!=i){
//exchange A[i] with A[largest]
temp=A[i];
A[i]=A[largest];
A[largest]=temp;
//use max_heapify()
max_heapify(A,largest,heap_size);
}
}
/*******************************************
*
* function build_max_heap();
*
* args
* A inttype array of heap elements
* heap_size inttype the length-1 of A
*
* ****************************************/
void build_max_heap(int A[],int heap_size){
int i,len;
len=heap_size;
//heap_size=len-1;
len=len/2;
// index i=floor(n/2) to 0 decarese
for(i=len;i>=0;i--)
max_heapify(A,i,heap_size);
}
/****************************************
*
* function heap_sort();
*
* args
* A intype array of heap elements
* heap_size inttype length of A,but
* heap_size=A.length-1
*
* return *pa pointer of A[0]
*
* *************************************/
int* heap_sort(int A[],int heap_size){
int i,len,temp;
int *pa;
build_max_heap(A,heap_size);
len=heap_size;
for(i=len;i>=1;i--){
/*first element exchange with A[i]
* to make sure the largest value of
* child node on the parent node
* */
temp=A[0];
A[0]=A[i];
A[i]=temp;
//decarese heap_size to move index of A
heap_size--;
// adjust max value to parent node
max_heapify(A,0,heap_size);
}
pa=A;
return pa;
}
int main()
{
int i,len,A[10],heap_size=0;
int* pa;
char c;
while(1){
scanf("%d",&A[heap_size]);
c=getchar();
if(c=='\n')
break;
heap_size++;
}
//use heap_sort()
pa=heap_sort(A,heap_size);
// output A after sorted
len=sizeof(A)/sizeof(int);
for(i=0;i<len;i++)
printf("%d ",*(pa+i));
return 0;
}
/*************************************
*
* input A[]={16,14,10,8,7,9,3,2,4,1}
*
* output A[]={1,2,3,4,7,8,9,10,14,16}
*
* ***********************************/
运行结果截图如下
以上便是堆排序中最大堆中排序的算法实现，有兴趣的朋友，可以留言，评论交流一下，一起进步。
