堆的应用
发布时间:2020-12-15 21:06:04 所属栏目:大数据 来源:网络整理
导读:一:堆排序算法 #include iostream#include math.husing namespace std;#define LEFT(i) (2*(i)+1)#define RIGHT(i) (2*(i)+2)// 16(0)// / // 10(1) 8(2)// / // 9(3) 7(4)//n为5,叶子节点序号为2,3,4 -floor(5/2).....nvoid exchange(int a,int b){in
一:堆排序算法 #include <iostream> #include <math.h> using namespace std; #define LEFT(i) (2*(i)+1) #define RIGHT(i) (2*(i)+2) // 16(0) // / // 10(1) 8(2) // / // 9(3) 7(4) //n为5,叶子节点序号为2,3,4 ->floor(5/2).....n void exchange(int& a,int& b) { int tmp=a; a=b; b=tmp; } void printArray(int a[],int n) { for(int i=0;i<n;++i) cout<<a[i]<<" "; cout<<endl; } void maxHeapify(int a[],int i,int n) // 使以i为根的子树成为最大堆 { int l=LEFT(i); int r=RIGHT(i); int heapindex=n-1; int largest; if((l<=heapindex)&&(a[l]>a[i])) largest=l; else largest=i; if((r<=heapindex)&&(a[r]>a[largest])) largest=r; if(largest!=i) { exchange(a[i],a[largest]); maxHeapify(a,largest,n); //由于大小对换了,所以对调的那个有可能就不满足最大堆的性质了 } } /* 构建最大堆 数组A[floor(n/2)..n]中的元素都是树中的叶子,所以要对树中的每一个其它节点调用maxHeapify(),让每一个 节点都满足最大堆的性质,注意顺序:从最后一个非叶子节点到根*/ void buildMaxHeap(int a[],int n) { for(int i=floor(n/2)-1;i>-1;--i) maxHeapify(a,i,n); } /*堆排序 先构建好最大堆,有最大堆性质可知根元素是最大的,把根与最后一个元素交换,让新根调用maxHeapify() */ void heapSort(int a[],int n) { buildMaxHeap(a,n); for(int i=n-1;i>0;--i) { exchange(a[0],a[i]); maxHeapify(a,i); } } int main() { int a[10]={16,4,10,14,7,9,2,8,1}; heapSort(a,10); printArray(a,10); cout<<endl; } 运行结果: 1 2 3 4 7 8 9 10 14 16 总结: 1.可以在线性时间内,将一个无序数组建成一个最大堆 2.堆排序时间复杂度为nlgn,但在实践中,快速排序往往优于堆排序 二:实现优先级队列 这里使用基于最大堆实现的最大优先级队列(模拟简单作业调度) #include <iostream> #include <stdlib.h> #include <string.h> #include <math.h> using namespace std; #define PARENT(i) ((int)floor(((i)-1)/2)) //堆中节点为i的父节点号(从0开始) #define LEFT(i) (2*(i)+1) #define RIGHT(i) (2*(i)+2) typedef struct job { unsigned jobid; //作业号 unsigned pid; //进程pid char name[10]; //作业name int priority; //优先级 }*Pjob; int current=0; //当前索引,从0开始 void exchange(char*& s,char*& d) { char *tmp=s; s=d; d=tmp; } void jobAdd(char **JobTable,Pjob p) { int i=current; JobTable[current]=(char*)p; while(i>0) { if(((Pjob)JobTable[i])->priority > ((Pjob)JobTable[PARENT(i)])->priority) //比较优先级 { exchange(JobTable[i],JobTable[PARENT(i)]); i=PARENT(i); //继续和上一级比较 } else break; } ++current; } void maxHeapify(char **JobTable,int i) //使以i为根的子树成为最大堆 { int l=LEFT(i); int r=RIGHT(i); int largest=i; if(l<=current-1&&((Pjob)JobTable[l])->priority > ((Pjob)JobTable[i])->priority) largest=l; if(r<=current-1&&((Pjob)JobTable[r])->priority > ((Pjob)JobTable[largest])->priority) largest=r; if(largest!=i) { exchange(JobTable[i],JobTable[largest]); maxHeapify(JobTable,largest); } } void doJob(char **JobTable) { Pjob now=(Pjob)JobTable[0]; cout<<"作业号:"<<now->jobid <<" "<<now->name <<" "<<now->pid <<" "<<now->priority<<" done!!!"<<endl; free(JobTable[0]); --current; if(current!=0) { JobTable[0]=JobTable[current]; maxHeapify(JobTable,0); //交换完后需要重新保持最大堆性质 } } int main() { char *JobTable[10]={0}; Pjob bash=(Pjob)malloc(sizeof(struct job)); bash->jobid=1; bash->pid=4321; strcpy(bash->name,"bash"); bash->priority=12; Pjob vi=(Pjob)malloc(sizeof(struct job)); vi->jobid=2; vi->pid=4325; strcpy(vi->name,"vivi"); vi->priority=16; Pjob perl=(Pjob)malloc(sizeof(struct job)); perl->jobid=4; perl->pid=4329; strcpy(perl->name,"perl"); perl->priority=20; Pjob qq=(Pjob)malloc(sizeof(struct job)); qq->jobid=3; qq->pid=4349; strcpy(qq->name,"qqqq"); qq->priority=30; Pjob cs=(Pjob)malloc(sizeof(struct job)); cs->jobid=5; cs->pid=4345; strcpy(cs->name,"cscs"); cs->priority=18; jobAdd(JobTable,bash); jobAdd(JobTable,vi); jobAdd(JobTable,perl); jobAdd(JobTable,qq); jobAdd(JobTable,cs); doJob(JobTable); doJob(JobTable); doJob(JobTable); doJob(JobTable); doJob(JobTable); cout<<endl; }运行结果: 作业号:3 qqqq 4349 30 done!!! 作业号:4 perl 4329 20 done!!! 作业号:5 cscs 4345 18 done!!! 作业号:2 vivi 4325 16 done!!! 作业号:1 bash 4321 12 done!!! 基于堆的优先级时间复杂度是lgn。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |