首页 > 代码库 > 堆与优先队列
堆与优先队列
当我们需要高效的完成以下操作时:
1.插入一个元素
2.取得最小(最大)的数值,并且删除
能够完成这种操作的数据结构叫做优先队列
而能够使用二叉树,完成这种操作的数据结构叫做堆(二叉堆)
堆与优先队列的时间复杂度:
若共有n个元素,则可在O(logn)的时间内完成上述两种操作
堆的结构如下图:
堆最重要的性质就是儿子的值一定不小于父亲的值,且堆从上到下,从左到右紧密排列。
堆的操作:
当我们希望向堆中插入元素时,堆的内部会进行如下操作(以插入元素3为例):
(1.在堆的末尾插入该值)
(2.不断向上提升该元素,直到满足堆的性质为止)
当我们需要删除堆中的最小值时,堆的内部则进行如下操作
(1.将堆的最后一个节点复制到根节点位置,而后删除最后一个节点)
(2.不断向下交换,直到满足堆的性质为止)
堆的代码实现:
int heap[MAXSIZE],hsize=0; void Push(int x) //向堆中添加元素 { int i = hsize++; //堆的大小增加 while(i > 0) { int father_id = (i - 1)/2; //父亲节点的编号 if(heap[i] > heap[father_id]) //判断是否满足堆的性质 break; heap[i] = heap[father_id]; //将父亲节点下放,将新增元素上移 i = father_id; } heap[i] = x; } void Pop() //弹出堆中的最小值 { int root = heap[0]; //记录最小值 int x = heap[hsize--]; //堆的大小减少 int i = 0; while(i * 2 + 1 < hsize) { int lson = i * 2 + 1; //左儿子节点 int rsong = lson + 1; //右儿子节点 if(lson > x && rson > x) //判断是否满足堆的性质 break; if(heap[lson] < heap[rson]) //选择与儿子交换 { heap[i] = heap[lson]; i = lson; } else if(ron < hsize) { heap[i] = heap[rson]; i = rson; } } heap[i] = x; return root; }
STL中的优先队列:
在C++中,STL里的priority_queue可以完成优先队列的实现,代码如下
#include<queue> #include<cstdio> using namespace std; int date[5]; int main() { priority_queue<int> Q; //默认为最大值优先 priority_queue<int,vector<int>,greater<int> > Q1; //最小值优先 priority_queue<int,vector<int>,less<int> > Q2; //最大值优先 for(int i=1;i<=3;i++) { scanf("%d",&date[i]); Q.push(date[i]); //插入元素 } while(!Q.empty()) { int x = Q.top(); //读取队头元素 Q.pop(); //弹出元素 printf("%d\n",x); } return 0; }
堆与优先队列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。