堆

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

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

            
                /** 最大堆的操作 */
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+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]);//DeleteMax
        PercDown(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);
    return0;
}