堆
优先队列：特殊的”队列”，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序 堆是优先队列的完全二叉树表示。 堆的两个特性： ①结构性：用数组表示的完全二叉树 ②有序性：任意结点的关键字是其子树所有结点的最大值，叫最大堆(或最小值，叫最小堆)(注意从根结点到任意结点路径上结点序列的有序性)
下面举一个最大堆的例子。
/** 最大堆的操作 */typedef struct HeapStruct *MaxHeap;struct HeapStruct {ElementType *Elements;Capacity;//堆的最大容量};MaxHeap Create(int MaxSize){/** 创建容量为MaxSize的最大堆 */MaxHeap H = malloc(sizeof(struct HeapStruct));H->Elements = malloc((MaxSize+1)*sizeof(ElementType));H->Size = 0;H->Capacity = MaxHeap;H->Elements[0] = MaxData;/** 定哨兵为大于堆中所有可能元素的值 便于以后的操作 */return H;}void Insert(MaxHeap H,ElementType item){/** 将元素item插入最大堆H */int i;if(IsFull(H)) {printf(“最大堆已满!\n”);return;}i = ++H->Size;//i指向插入后堆中的最后一个元素的位置for( ; H->Elements[i/2] > item && i > 1; i /= 2) {H->Elements[i] = H->Elements[i/2];//向下过滤结点}H->Elements[i] = item;//将item插入}ElementType DeleteMax(MaxHeap H){/** 从最大堆H中取出键值为最大的元素，并删除一个结点 */int Parent,Child;ElementType MaxItem,temp;if(IsEmpty(H)) {printf(“最大堆已空!\n”);return;}MaxItem = H->Elements[1];//取出根结点最大值/** 用最大堆中最后一个元素从根节点开始向上过滤下层结点 */temp = H->Elements[H->Size–];for(Parent = 1 ; Parent*2 <= H->Size; Parent = Child) {Child = Parent*2;if((Child != H->Size) && (H->Elements[Child+1] > H->Elements[Child]))Child ++;//Child指向左右子结点的较大者if(temp >= H->Elements[Child]) break;else H->Elements[Parent] = H->Elements[Child];//移动temp元素到下一层}H->Elements[Parent] = temp;return MaxItem;}选择排序
选择排序(Selection Sort)的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。 简单选择排序：没啥好说的，代码如下
void SelectSort(SqList &L){//对顺序表L作简单选择排序for(i = 1 ; i < L.lenth ; ++i) {//选择第i小的记录，并交换到位j = SelectMinKey(L,i);//选择最小的记录if(i != j) swap(L[i],L[j]);//与第i个记录交换}}//SelectSort
树形选择排序：可被堆排序替代，故不再详述
堆排序
先看一种使用堆的简单的O(nlogn)算法
void Heap_Sort(ElementType A[],int N){BuildHeap(A);//建立最小堆for(i = 0 ; i < N ; i ++)TmpA[i] = DeleteMin(A);//取出堆中最小的元素并返回给TmpAfor(i = 0 ; i < N ; i ++)A[i] = TmpA[i];//导回原数组}
真正的堆排序不是建立最小堆而是建立最大堆，，每次将最大堆的根和最后一个元素交换，再维护成最大堆，这样直到都交换完毕。代码如下
void Heap_Sort(ElementType A[],int N){/** PercDown(A,a,b)表示在A中考虑前b-1个 把第a个元素下移到该在的位置 */for(i = N/2 ; i >= 0 ; i –)PercDown(A,i,N);//BuildHeapfor(i = N-1 ; i > 0 ; i –) {Swap(&A[0],&A[i]);//DeleteMaxPercDown(A,0,i);}}
下面来做一个排序实验，将 int s[20] = {11,5,12,6,7,14,20,2,15,3,17,13,1,18,9,4,16,8,10,19}; 这组数据分别用简单选择排序和堆排序处理，分别重复一千万次， 结果如下
如果我们把数据加到30个：
这也说明，对于大数据(当然这里只是假设)堆排序是高效的。 下面是实验代码：
#include <cstdio>#include <ctime>int main(){int t = 10000000;int start = clock();while(t–) {int s[30] = {30,11,29,5,12,6,21,7,23,14,20,22,28,2,15,3,17,13,1,25,18,9,4,16,24,8,10,27,19,26};for(int i = 0 ; i < 29 ; i ++) {//确定第i个元素int k,mi=31;for(int j = i ; j < 30 ; j ++) {if(mi > s[j]) {mi = s[j];k = j;}}if(i != k) {int tmp = s[i];s[i] = s[k];s[k] = tmp;}}}/** 简单选择排序 */int _end = clock();printf(“简单选择排序需要%dms\n”,_end-start);t = 10000000;start = clock();while(t–) {int s[30] = {30,11,29,5,12,6,21,7,23,14,20,22,28,2,15,3,17,13,1,25,18,9,4,16,24,8,10,27,19,26};for(int i = 14; i >= 0 ; i –) {/** s[i]换到该换的位置上 */int par = i;for(int child = 2*par+1 ; child < 30 ; child = 2*par+1) {if(child != 29 && s[child] < s[child+1]) child++;if(s[par] >= s[child]) break;else {int tmp = s[par];s[par] = s[child];s[child] = tmp;}par = child;}}for(int i = 29 ; i >= 1 ; i –) {int tmp = s[i];s[i] = s[0];s[0] = tmp;/** 将s[0]换至合适的位置 考虑0-(i-1)元素 */int par = 0;for(int child = par*2+1; child < i ; child = par*2+1) {if(child != i-1 && s[child] < s[child+1]) child++;if(s[par] >= s[child]) break;else {int tmp = s[par];s[par] = s[child];s[child] = tmp;}par = child;}}}/** 堆排序 */_end = clock();printf(“堆排序需要%dms\n”,_end-start);return 0;}
人之所以能，是相信能。
