使用二叉堆来实现优先队列,可以应用与图的最短路径,最小生成树等算法。优先队列包含一下功能,buildHeap_MIN,效率为O(N), extract_MIN,效率为O(logN), decrease_key,效率为O(logN)等。
#include<iostream> #include<string.h> #include<fstream> using namespace std; class node { public: int key,value; node() { key=-1; value=-1; } }; class priority_queue { public: const static int maxm=1005; node array[maxm]; int index[maxm]; int flag; priority_queue() { this->flag=0; } priority_queue(int flag) { this->flag=flag-1; } void heapify_MIN() { int n=flag/2+flag%2-1; for(int i=n;i>=0;i--) buildHeap_MIN(i,flag); } void buildHeap_MIN(int k,int m) { int j=2*k+1; if(j>m) return; if(j+1<=m&&array[j].value>array[j+1].value) j=j+1; if(array[k].value>array[j].value) { int a=array[k].key; int b=array[j].key; index[a]=j; index[b]=k; node temp=array[k]; array[k]=array[j]; array[j]=temp; buildHeap_MIN(j,m); } } node extract_MIN() { node res=array[0]; int a=array[0].key; int b=array[flag].key; index[a]=flag; index[b]=0; node temp=array[0]; array[0]=array[flag]; array[flag]=temp; this->flag--; buildHeap_MIN(0,flag); return res; } void decrease_key(int k,int key) { if(k==0&&key<array[k].value) { array[k].value=key; return; } if(array[k].value<=key) return; else { int n=k/2+k%2-1; if(array[n].value>key) { int a=array[k].key; int b=array[n].key; index[a]=n; index[b]=k; node temp=array[k]; array[k]=array[n]; array[n]=temp; decrease_key(n,key); } else { array[k].value=key; return; } } } }; int cases,n,dist; const int maxm=10000; int graphMatrix[1001][1001]; int favorate[1001]; int s[1001]; int path[1001]; int main() { /*ifstream txtfile; txtfile.open("e:\\zoj\\zoj_1586.txt"); if(!txtfile) { cerr<<"open error"<<endl; exit(1); } txtfile>>cases;*/ cin>>cases; while(cases--) { //txtfile>>n; cin>>n; for(int i=0;i<n;i++) { //txtfile>>favorate[i]; cin>>favorate[i]; } //memset(graphMatrix,0,sizeof(graphMatrix)); memset(s,0,sizeof(s)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { //txtfile>>dist; cin>>dist; graphMatrix[i][j]=dist+favorate[i]+favorate[j]; } priority_queue q(n-1); for(int i=1;i<n;i++) { path[i]=0; s[i]=0; } path[0]=0; s[0]=1; for(int i=0;i<n-1;i++) { q.array[i].value=graphMatrix[0][i+1]; q.array[i].key=i+1; } for(int i=1;i<n;i++) { q.index[i]=i-1; } q.heapify_MIN(); int result=0; for(int i=1;i<n;i++) { node p=q.extract_MIN(); s[p.key]=1; result+=p.value; //cout<<p.key<<" "; for(int j=1;j<n;j++) { if(s[j]==0&&j!=p.key) { int index=q.index[j]; if(graphMatrix[p.key][j]<q.array[index].value) { q.decrease_key(index,graphMatrix[p.key][j]); path[j]=p.key; } } } } //cout<<endl; cout<<result<<endl; } return 0; }
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1242http://acm.zju.edu.cn/on ... -
BFS与双向BFS---zoj_1505
2011-10-09 17:14 1652http://acm.zju.edu.c ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1720http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1325Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 875首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1289朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1677题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2497AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1196二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2144网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 873trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 924bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1080我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1667LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2853zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1375染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 763线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 783快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3087斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1292本文大量 ...
相关推荐
[9.8.1]--608优先队列和二叉堆.srt
[9.8.1]--608优先队列和二叉堆.mp4
利用优先队列(大顶堆)解决轮廓线问题,广东工业大学教程,还不错的
本ppt讲解了优先队列的五种实现方式,即二叉堆、d叉堆、左式堆、斜堆、二项堆。
优先队列的基本结构:二叉堆、d堆、左式堆、斜堆
主要介绍了java编程实现优先队列的二叉堆代码分享,具有一定参考价值,需要的朋友可以了解下。
优先队列通常使用二叉堆(包括最大堆和最小堆)来实现,因为堆的性质使得插入和删除最大(或最小)元素的操作可以在对数时间内完成。这使得优先队列在处理大量数据时具有高效的性能。 总的来说,优先队列是一种非常...
优先队列的实现通常依赖于其他数据结构,如二叉堆、斐波那契堆等。这些数据结构能够有效地维护元素的优先级顺序,使得插入、删除和查找等操作都能够在对数时间复杂度内完成。特别是二叉堆,由于其具有堆属性(即任意...
c#编写的基于有序数组、无序数组、集合、二叉堆的四种优先队列,已测试可用。
优先队列的二叉堆实现 在前面的章节里我们学习了“先进先出”(FIFO)的数据结构:队列(Queue)。队列有一种变体叫做“优先队列”(Priority Queue)。优先队列的出队(Dequeue)操作和队列一样,都是从队首出队。...
本文简要介绍一种基于数组二叉堆实现的优先队列,定义的数据结构和实现的函数接口说明如下: 一、键值对结构体:KeyValue 代码如下:// =============KeyValue Struct==================================typedef ...
- [5-3 二叉堆](5.3_binaryHeap.py) - [5-4 二叉搜索树](5.4_binarySearchTree.py) - [5-5 平衡二叉树](5.5_avlTree.py) - [5-6 红黑树](5.6_rbTree.py) - [5-7 trie](5.7_trie.py) - [5-8 双数组字典树](5.8_datree...
二叉查找树是以一种特殊的二叉树... 遍历元素:遍历主要有中序、前序、后序、深度优先、广度优先等。 下面这个类包括了结点的定义还有二叉树的定义。 package binaryTree; public class BinaryTree { //
链表、双链表、队列、Stack、哈希表、堆 - 最大和最小堆、优先队列、Trie、树、二叉搜索树、AVL树、红黑树、区段树 - 包含最小/最大/总和范围查询示例、Fenwick Tree(二叉索引树)、图形(有向和无向)、 Disjoint ...
包含的数据结构链表字典 -多词典关联词典默认字典 -二叉搜索树键值对的二叉搜索树堆队列设置 -包二叉堆优先队列它还包括几个用于操作数组的函数。用法npm install typescript-collections --save ES6 import ... ...
leetcode 分类 Algorithm-Practice-EveryWeek ...考查二叉堆,优先队列 2019-12-12-全排列下一个数leetcode31 Leetcode 31【难度中等】 考查字典序算法 2019-12-17-堆排序 无,练习题 2019-12-22-Leetcode108
- 二叉堆 - 左式堆 - 二项队列 ###第七章 - 插入排序 - 希尔排序 - 堆排序 - 归并排序 - 快速排序 ###第八章 -不相交集 ###第九章 -邻接表(Versioni 1,2) -拓扑排序(Versioni 1,2) -单源最短路径算法 -最大网络流 -...
Huffman-Coding-Using-... 这是使用 JAVA 中实现的优先队列(使用最小堆)、二叉搜索树和链表等数据结构的霍夫曼编码的实现。 该项目可以对任何类型的文本文件进行无损数据压缩。 应用程序还可以解码以取回原始文件。
精心整理史上最全的数据结构flash演示动画,共5个版本,祝大家考研成功! \数据结构flash演示\版本1 \数据结构flash演示\版本2 ...\数据结构flash演示\版本2\3.4 队列-数组型队列删除队首元素.swf