堆.cpp

1、问题描述：
给出两个长度为n的有序表A和B，在A和B中各任取一个，可以得到n^2个和。求这些和最小的n个。

2、算法分析：
可以把这些和看成n个有序表：
A[1]+B[1]<=A[1]+B[2]<=A[1]+B[3]<=…
A[2]+B[1]<=A[2]+B[2]<=A[2]+B[3]<=…
…
A[n]+B[1]<=A[n]+B[2]<=A[n]+B[3]<=…
类似刚才的算法，每次O(logn),共取n次最小元素，共O(nlogn)

思路主要是为n^2个和建立小顶堆，然后每次取堆顶元素，即删除堆顶节点时，用堆尾结点代替堆顶结点，不会破坏其左右字数的堆的特性，但需要对新的堆顶结点进行调整，以维护堆的特性。对堆进行筛选操作的算法复杂度是O(logn)，因为要取n个最小元素，所以共O(nlogn)。具体实现参考大二上学期学的数据结构校内教材。

3、测试

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;     //用作函数值类型，表示函数结果状态
typedef int ElemType;
typedef int KeyType;    //关键字类型为整数类型
typedef struct{
    KeyType key;    //关键字项
    //...           //其他数据项
}RecordType, RcdType;   //记录类型，RcdType为RecordType的简写

typedef struct{
    RcdType *rcd;   //基地址，0号单元不用
    int n;  //堆长度
    int size;   //堆容量
    int tag;    //小顶堆与大顶堆的标志：tag=0为小顶堆，tag=1为大顶堆
    int (*prior)(KeyType, KeyType); //函数变量，用于关键字优先级比较
}Heap;  //堆类型

int greatPrior(int x, int y){return x>=y;}      //大顶堆优先函数
int lessPrior(int x, int y){return x<=y;}       //小顶堆优先函数

//函数接口
/*1.初建最大容量为size的空堆H，当tag为0或1时分别表示小顶堆和大顶堆，prior为相应的优先函数*/
Status InitHeap(Heap &H, int size, int tag, int(*prior)(KeyType, KeyType));
/*2.用E建长度为n的堆H，容量为size，当tag为0或1时分别表示小顶堆和大顶堆，prior为相应的优先函数*/
void MakeHeap(Heap &H, RcdType *E, int n, int size, int tag, int(*prior)(KeyType, KeyType));
/*3.销毁堆H*/
Status DestroyHeap(Heap &H);
/*4.对位置为pos的结点做筛选*/
void ShiftDown(Heap &H, int pos);
/*5.将e插入堆*/
Status InsertHeap(Heap &H, RcdType e);
/*6.删除堆顶结点，用e返回其值*/
Status RemoveFirstHeap(Heap &H, RcdType &e);
/*7.删除位置pos的结点，用e返回其值*/
Status RemoveHeap(Heap &H, int pos, RcdType &e);
/*8.交换指定两个的结点*/
Status swapHeapElem(Heap &H, int i, int j);



/*1.初建最大容量为size的空堆H，当tag为0或1时分别表示小顶堆和大顶堆，prior为相应的优先函数*/
Status InitHeap(Heap &H, int size, int tag, int(*prior)(KeyType, KeyType)){
    H.rcd = (RcdType *)malloc((size+1)*sizeof(RcdType));    //分配存储空间,0号单元不用，作为哨兵
    if(NULL==H.rcd)
        return OVERFLOW;
    H.size = size;
    H.tag = tag;
    H.prior = prior;
}

/*2.用E建长度为n的堆H，容量为size，当tag为0或1时分别表示小顶堆和大顶堆，prior为相应的优先函数*/
void MakeHeap(Heap &H, RcdType *E, int n, int size, int tag, int(*prior)(KeyType, KeyType)){
    int i;
    H.rcd = E;  //E[1..n]是堆的n个结点，0号单元空闲
    H.n = n;
    H.size = size;
    H.tag = tag;
    H.prior = prior;
    for(i=n/2; i>0; i--){
        ShiftDown(H, i);
    }
}

/*3.销毁堆H*/
Status DestroyHeap(Heap &H){
    H.n = 0;
    H.size = 0;
    free(H.rcd);    //释放指针指向的内存
    H.rcd = NULL;   //把基址设为null,悬空。防止指针在后面不小心又被解引用了。
    return OK;
}

/*8.交换指定两个的结点*/
Status swapHeapElem(Heap &H, int i, int j){
    RcdType t;
    if(i<0 || i>H.n || j<0 || j>H.n)
        return ERROR;
    t = H.rcd[i];
    H.rcd[i] = H.rcd[j];
    H.rcd[j] = t;
    return OK;
}

/*4.对位置为pos的结点做筛选,向下调整*/
void ShiftDown(Heap &H, int pos){
    int c, rc;
    while(pos <= H.n/2){//若pos结点为叶子结点，循环结束
        c = pos * 2;  //pos结点的左孩子位置
        rc = pos * 2 + 1; //pos结点的右孩子位置
        if(rc <= H.n && H.prior(H.rcd[rc].key, H.rcd[c].key))   c = rc; //比较谁优先
        if(H.prior(H.rcd[pos].key, H.rcd[c].key))
           return;  //若pos结点较优先，则筛选结束
        swapHeapElem(H, pos, c);    //否则和较优先者c交换位置
        pos = c;    //继续向下调整
    }
}

/*5.将e插入堆，向上调整*/
Status InsertHeap(Heap &H, RcdType e){
    int curr;
    if(H.n >= H.size-1)
        return ERROR;   //堆已满，插入失败
    curr = ++H.n;
    H.rcd[curr] = e;    //将插入元素加到堆尾
    while(1 != curr && H.prior(H.rcd[curr].key, H.rcd[curr/2].key)){
        swapHeapElem(H, curr, curr/2);  //向上调整
        curr /= 2;
    }
    return OK;
}

/*6.删除堆顶结点，用e返回其值*/
Status RemoveFirstHeap(Heap &H, RcdType &e){
    if(H.n <= 0)
        return ERROR;
    e = H.rcd[1];   //取出堆顶结点
    swapHeapElem(H, 1, H.n);
    H.n--;          //交换堆顶与堆尾结点，堆长度减1
    if(H.n > 1)
        ShiftDown(H, 1);    //向下筛选
    return OK;
}

/*7.删除位置pos的结点，用e返回其值*/
Status RemoveHeap(Heap &H, int pos, RcdType &e){
    if(pos > H.n || pos <0 || H.n <=0)
        return ERROR;
    e = H.rcd[pos]; //取出位置pos的结点
    swapHeapElem(H, pos, H.n);
    H.n--;          //交换位置pos的结点与堆尾结点，堆长度减1
    if(H.n > 1)
        ShiftDown(H, pos);  //向下筛选
    return OK;
}

/*9.堆排序*/
void HeapSort(RcdType *L, int length, int size){
    //若大顶堆，排序结果为从小到大排序
    //若小顶堆，排序结果为从大到小排序
    Heap H;
    int i;
    RcdType e;
    MakeHeap(H, L, length, size, 1, greatPrior);    //待排序列建大顶堆
    for(i=H.n; i>0; i--){
        RemoveFirstHeap(H,e);   //堆顶与堆尾结点交换，堆长度减1，筛选新的堆顶结点
    }
}

int main()
{
    //作者：ZXP-2017/12/27
    //应用：序列和的前n小元素(优先队列)
    int i =1;
    int j = 1;
    int k = 1;
    int list_num = 0;
    printf("Please input the number of list:");
    scanf("%d", &list_num);

    RcdType *A = (RcdType *)malloc(list_num * sizeof(RcdType) + 1);     //0号元素未用
    RcdType *B = (RcdType *)malloc(list_num * sizeof(RcdType) + 1);     //0号元素未用
    RcdType *L = (RcdType *)malloc(list_num * list_num * sizeof(RcdType) + 1);  //0号元素未用

    printf("Please input A list:");
    for(i=1;i<=list_num;i++)
        scanf("%d",&A[i].key);

    printf("Please input B list:");
    for(i=1;i<=list_num;i++)
        scanf("%d",&B[i].key);

    for(i=1,k=1; i<= list_num; i++){
        for(j=1; j<=list_num; j++){
            L[k].key = A[i].key + B[j].key;
            k++;
        }
    }

    HeapSort(L, list_num * list_num, list_num * list_num);

    printf("Sequence n small elements are:");
    for(i=1; i<=list_num; i++){
        printf("%d ", L[i].key);
    }
    return 0;
}