本文共 1696 字，大约阅读时间需要 5 分钟。
#include//#include //#include #define N 10/* * 堆大小 * */int heapSize = 0;/* * 返回左子节点索引,root_index 堆顶索引 * */int left_child_index(int root_index){ return ((root_index << 1) + 1);}/* * 返回右子节点索引,root_index 堆顶索引 * */int right_child_index(int root_index){ return ((root_index << 1) + 2);}void swap(int *x,int *y){ int tmp = *x; *x = *y; *y = tmp;}void show(int arr[],int len){ int i; for(i = 0; i < len; i++) printf("%3d",arr[i]); printf("\n");}void maxHeapify(int arr[],int root_index){ int largest = 0; int left = left_child_index(root_index); int right = right_child_index(root_index); /* * 把largest赋值为推顶和其左子节点中较大的 * */ if((left <= heapSize) && (arr[left] > arr[root_index])) largest = left; else largest = root_index; /* * 把largest赋值为推顶和其右子节点中较大的 * */ if((right <= heapSize) && (arr[right] > arr[largest])) largest = right; /* * 此时largest 是堆顶，左子节点，右子节点三者中最大的 * */ if(largest != root_index) { /* * 如果堆顶不是最大的，则交换，并递归调整 * */ swap(&arr[largest],&arr[root_index]); maxHeapify(arr,largest); }}/* * 初始化堆，将数组中每一个元素放到合适的位置 * 完成后，堆顶元素为数组中最大的数 * */void buildMaxHeap(int arr[],int len){ int i; heapSize = len; /* * i表示堆顶高度 * */ for(i = (len >> 1); i >= 0; i--) maxHeapify(arr,i);}void heap_sort(int arr[],int len){ buildMaxHeap(arr,(len - 1)); int i; for(i = (len - 1); i >= 1; i--) { /* * 堆顶元素arr[0] 被置换到数组尾部arr[i] * */ swap(&arr[0],&arr[i]); /* * 从堆中移除改元素 * */ heapSize--; /* * 重建堆,先默认第一个元素就是最大 * */ maxHeapify(arr,0);#ifdef DEBUG show(arr,N);#endif }}int main(){ srand(time(0)); int i; int arr[N] = {-1}; for(i = 0; i < N; i++) arr[i] = rand() % 101; show(arr,N); heap_sort(arr,N); show(arr,N);}此为大根排序，小跟排序52,60行改成小于即可,编译时定义DEBUG可以看到排序的过程
转载地址：http://xxuhj.baihongyu.com/