堆

优先队列：特殊的”队列”，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序
堆是优先队列的完全二叉树表示。
堆的两个特性：
①结构性：用数组表示的完全二叉树
②有序性：任意结点的关键字是其子树所有结点的最大值，叫最大堆(或最小值，叫最小堆)(注意从根结点到任意结点路径上结点序列的有序性)

下面举一个最大堆的例子。

/** 最大堆的操作 */
typedef struct HeapStruct *MaxHeap;
struct HeapStruct {
    ElementType *Elements;//存储堆元素的数组
    int Size;//堆大小
    int Capacity;//堆的最大容量
};
MaxHeap Create(int MaxSize)
{
    /** 创建容量为MaxSize的最大堆 */
    MaxHeap H = malloc(sizeof(struct HeapStruct));
    H->Elements = malloc((MaxSize+@H_404_37@1)*sizeof(ElementType));
    H->Size = @H_404_37@0;
    H->Capacity = MaxHeap;
    H->Elements[@H_404_37@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/@H_404_37@2] > item && i > @H_404_37@1; i /= @H_404_37@2) {
        H->Elements[i] = H->Elements[i/@H_404_37@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[@H_404_37@1];//取出根结点最大值
    /** 用最大堆中最后一个元素从根节点开始向上过滤下层结点 */
    temp = H->Elements[H->Size--];
    for(Parent = @H_404_37@1 ; Parent*@H_404_37@2 <= H->Size; Parent = Child) {
        Child = Parent*@H_404_37@2;
        if((Child != H->Size) && (H->Elements[Child+@H_404_37@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 = @H_404_37@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 = @H_404_37@0 ; i < N ; i ++)
        TmpA[i] = DeleteMin(A);//取出堆中最小的元素并返回给TmpA
    for(i = @H_404_37@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/@H_404_37@2 ; i >= @H_404_37@0 ; i --)
        PercDown(A,i,N);//BuildHeap
    for(i = N-@H_404_37@1 ; i > @H_404_37@0 ; i --) {
        Swap(&A[@H_404_37@0],&A[i]);//DeleteMax
        PercDown(A,@H_404_37@0,i);
    }
}

下面来做一个排序实验，将
int s[20] = {11,5,12,6,7,14,20,15,3,17,13,1,18,9,4,16,8,10,19};
这组数据分别用简单选择排序和堆排序处理，分别重复一千万次，
结果如下

如果我们把数据加到30个：

这也说明，对于大数据(当然这里只是假设)堆排序是高效的。
下面是实验代码：

#include <cstdio>
#include <ctime>
int main()
{
    int t = @H_404_37@10000000;
    int start = clock();
    while(t--) {
        int s[@H_404_37@30] = {@H_404_37@30,@H_404_37@11,@H_404_37@29,@H_404_37@5,@H_404_37@12,@H_404_37@6,@H_404_37@21,@H_404_37@7,@H_404_37@23,@H_404_37@14,@H_404_37@20,@H_404_37@22,@H_404_37@28,@H_404_37@2,@H_404_37@15,@H_404_37@3,@H_404_37@17,@H_404_37@13,@H_404_37@1,@H_404_37@25,@H_404_37@18,@H_404_37@9,@H_404_37@4,@H_404_37@16,@H_404_37@24,@H_404_37@8,@H_404_37@10,@H_404_37@27,@H_404_37@19,@H_404_37@26};
        for(int i = @H_404_37@0 ; i < @H_404_37@29 ; i ++) {//确定第i个元素
            int k,mi=@H_404_37@31;
            for(int j = i ; j < @H_404_37@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 = @H_404_37@10000000;
    start = clock();
    while(t--) {
        int s[@H_404_37@30] = {@H_404_37@30,@H_404_37@26};
        for(int i = @H_404_37@14; i >= @H_404_37@0 ; i --) {
            /** s[i]换到该换的位置上 */
            int par = i;
            for(int child = @H_404_37@2*par+@H_404_37@1 ; child < @H_404_37@30 ; child = @H_404_37@2*par+@H_404_37@1) {
                if(child != @H_404_37@29 && s[child] < s[child+@H_404_37@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 = @H_404_37@29 ; i >= @H_404_37@1 ; i --) {
            int tmp = s[i];
            s[i] = s[@H_404_37@0];
            s[@H_404_37@0] = tmp;
            /** 将s[0]换至合适的位置 考虑0-(i-1)元素 */
            int par = @H_404_37@0;
            for(int child = par*@H_404_37@2+@H_404_37@1; child < i ; child = par*@H_404_37@2+@H_404_37@1) {
                if(child != i-@H_404_37@1 && s[child] < s[child+@H_404_37@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 @H_404_37@0;
}