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