堆.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;
}

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,053评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,527评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,779评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,685评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,699评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,609评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,989评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,654评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,890评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,634评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,716评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,394评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,976评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,950评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,191评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,849评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,458评论 2 342

推荐阅读更多精彩内容