一种高效的动态优先队列数据结构

doi:10.16182/j.issn1004731x.joss.201701013

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (1): 91-98.doi: 10.16182/j.issn1004731x.joss.201701013

一种高效的动态优先队列数据结构

祁彬斌, 庞明勇

南京师范大学教育技术系,江苏南京 210097

收稿日期:2015-04-24 修回日期:2015-07-07 出版日期:2017-01-08 发布日期:2020-06-01
作者简介:祁彬斌(1991-),男,江苏盐城,博士生,研究方向为数字几何处理;庞明勇(1968-),男,安徽淮南,博士,教授,博导,研究方向为数字几何处理。
基金资助:
国家自然科学基金(41271383, 60873175),江苏省现代教育技术研究课题(2014-R-33356)

Efficient Priority Queue Constructed on Heap-like Data Structure

Qi Binbin, Pang Mingyong

Department of Educational Technology, Nanjing Normal University, Nanjing 210097, China

Received:2015-04-24 Revised:2015-07-07 Online:2017-01-08 Published:2020-06-01

摘要/Abstract

摘要： 数据结构的组织形式在算法实现中占有重要地位。探讨了优先队列中的数据结构组织问题,给出一种高效的堆式队列数据组织结构,阐明了该数据结构的基本操作,理论上分析了其时间和空间性能,通过实验和应用实例验证了堆式队列数据结构动态存取效率的高效性、存储空间的自适应性以及实现上的简单性。实验结果表明,堆式优先队列数据结构可有效地提高各类仿真系统的性能,也可用于组合优化等多种应用问题的解决。

关键词: 数据结构, 优先队列, 堆式队列, 算法效率

Abstract: How to organize data structure is a very important issue for various algorithm implementations. In this paper, a novel and efficient priority-queue was presented based on a kind of heap-like data structure. The organization structure of the queue is first introduced and then a set of basic operators on the queue were elucidated, the time and space performances of the data structure was also theoretically analyzed. Our data structure has several advantages, including the adaptability of storage space as well as the simplicity and convenience of implementation. Experimental results showed that the heuristic priority queue data structure can effectively improve the performance of various types of simulation systems, relative to its traditional counterparts. Our data structure can be used to solve a variety of application problems such as combinatorial optimization.

Key words: data structure, priority queue, heap-like queue, efficiency of algorithm

中图分类号:

TP391

祁彬斌, 庞明勇. 一种高效的动态优先队列数据结构[J]. 系统仿真学报, 2017, 29(1): 91-98.

Qi Binbin, Pang Mingyong. Efficient Priority Queue Constructed on Heap-like Data Structure[J]. Journal of System Simulation, 2017, 29(1): 91-98.

参考文献

[1] 高文宇, 王建新, 陈松乔. 网络仿真软件NS2中队列调度算法的扩展[J]. 系统仿真学报, 2006, 18(2): 521-525.
Gao W Y, Wang J X, Chen S Q.Extension of queue scheduling algorithm in NS2[J]. Journal of System Simulation, 2016, 18(2): 521-525.
[2] Coming D S, Staadt O G.Kinetic sweep and prune for multi-body continuous motion[J]. Computers & Graphics (S0097-8493), 2006, 30(3): 439-449.
[3] 李红波, 赵永耀, 吴渝, 等. 一种基于距离约束的改进SURF算法[J]. 系统仿真学报, 2014, 26(12): 2944-2956.
Li H B, Zhao Y Y, Wu Y, et al.Improved SURF algorithm based on distance constraint[J]. Journal of System Simulation, 2014, 26(12): 2944-2956.
[4] Cris L, Luengo H.Revisiting priority queues for image analysis[J]. Pattern Recognition (S0031-3203), 2010, 43(9): 3003-3012.
[5] 李凤霞, 赵邓, 李仲君. 基于外观保持的多分辨率模型生成算法[J]. 系统仿真学报, 2012, 24(1): 62-66.
Li F X, Zhao D, Li Z J.Mesh simplification for 3D models with exterior maintaining[J]. Journal of System Simulation, 2012, 24(1): 62-66.
[6] Zhang C, Wang K, Mu H.A priority queue algorithm for the replication task in hbase[J]. Journal of Software (S1796-217X), 2013, 8(7): 1765-1769.
[7] Liu F, Fu C H.Improving mobile network performance with two queueing buffer allocations of priority-based queueing scheme[J]. Wireless Networks (S1022-0038), 2014, 20(6): 1349-1367.
[8] 杨神化, 施朝健, 关克平, 等. 基于MAS和SHS智能港口交通流模拟系统的开发与应用[J]. 系统仿真学报, 2007, 19(2): 289-292.
(Yang S H, Shi C J, Guan K P, et al.Intelligent simulation of traffic flow in port area with MAS and SHS[J]. Journal of System Simulation, 2007, 19(2): 289-292.)
[9] 庞明勇, 卢章平. 网格数据处理中的数据结构组织[J]. 计算机工程与应用, 2004, 40(6): 91-93.
(Pang M Y, Lu Z P.Data structure for calculating meshes[J]. Computer Engineering and Applications, 2004, 40(6): 91-93.)
[10] Cormen T H, Leiserson C E, Rivest R L, et al.Introduction to algorithms [M]. Cambridge, USA: MIT Press, 2001.
[11] Tarjan R E.Amortized computational complexity[J]. SIAM Journal on Algebraic Discrete Methods (S0186-5212), 1985, 6(2): 306-318.
[12] Fredman M L, Sedgewick R, Sleator D D, et al.The pairing heap: a new form of self-adjusting heap[J]. Algorithmica (S0178-4617), 1986, 3(1): 111-129.
[13] Pettie S.Towards a final analysis of pairing heaps[C]// Proceedings of the 2005 (46^th) Annual IEEE Symposium on Foundations of Computer Science. USA: IEEE, 2005: 174-183.
[14] 李建中, 张艳秋. 基于蛇型磁带的海量数据排序算法[J]. 软件学报, 2003, 14(1): 28-34.
(Li J Z, Zhang Y Q.A massive data sort algorithm based on serpentine tape[J]. Journal of Software, 2003, 14(1): 28-34.)
[15] Subramani K, Madduri K.Two-level heaps: a new priority queue structure with applications to the single source shortest path problem[J]. Computing (S0010-485X), 2010, 90(3/4): 113-130.
[16] Guo W, Zhang B, Chen G, et al. A PSO-optimized minimum spanning tree-based topology control scheme for wireless sensor networks [J]. International Journal of Distributed Sensor Networks (S1550-1329), 2013: Article ID 985410.
[17] 汪闽, 周成虎, 裴韬, 等. 一种带控制节点的最小生成树聚类方法[J]. 中国图象图形学报, 2002, 7(8): 765-770.
(Wang M, Zhou C H, Pei T, et al.A MST based clustering method with controlling vertexes[J]. Journal of Image and Graphics, 2002, 7(8): 765-770.)
[18] 黎莹, 戴芳, 郝勇, 等. 基于最小生成树的图像分割[J]. 计算机工程与应用, 2013, 49(13): 149-151.
(Li Y, Dai F, Hao Y, et al.Image segmentation based on minimum spanning tree[J]. Computer Engineering and Applications, 2013, 49(13): 149-151.)
[19] Fabijańska A, Gocławski J.New accelerated graph-based method of image segmentation applying minimum spanning tree[J]. IET Image Processing (S1751-9659), 2014, 8(4): 239-251.
[20] 杨国慧, 周春光, 黄艳新, 等. 最小生成树用于基因表示数据的聚类算法[J]. 计算机研究与发展, 2003, 40(10): 1431-1435.
(Yang G H, Zhou C G, Huang Y X, et al.An algorithm for clustering gene expression data using minimum spanning trees[J]. Journal of Computer Research and Development, 2003, 40(10): 1431-1435.)
[21] 周康, 李刚, 谢振林, 等. 最小生成树DNA算法[J]. 华中科技大学学报(自然科学版), 2012, 40(1): 30-34.
(Zhou K, Li G, Xie Z L, et al.DNA algorithm of minimal spanning tree problem[J]. Journal of Huazhong University of Science and Technology (Nature Science), 2012, 40(1): 30-34.)
[22] Neumann F, Witt C.Ant colony optimization and the minimum spanning tree problem[J]. Theoretical Computer Science (S0304-3975), 2010, 411(25): 2406-2413.

一种高效的动态优先队列数据结构

Efficient Priority Queue Constructed on Heap-like Data Structure

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	李智杰, 石昊琦, 李昌华, 张颉. 基于改进遗传算法的影像中心布局优化方法[J]. 系统仿真学报, 2022, 34(6): 1173-1184.
[2]	陆淼嘉, 黄承媛, 滕靖. 基于多智能体的网购生鲜无人车配送调度仿真[J]. 系统仿真学报, 2022, 34(6): 1185-1195.
[3]	陈斌, 刘悦, 杨亚磊. 基于STN的机场航班过站保障时间协同规划建模[J]. 系统仿真学报, 2022, 34(6): 1196-1207.
[4]	窦欣宇, 陈晓辉, 梁德群, 林彬. 一种高谱效海上甚高频通信技术及其仿真研究[J]. 系统仿真学报, 2022, 34(6): 1208-1218.
[5]	段绍米, 罗会龙, 刘海鹏. 人群搜索和樽海鞘群的混合算法优化PID参数[J]. 系统仿真学报, 2022, 34(6): 1230-1246.
[6]	杨凯, 陈纯毅, 胡小娟, 于海洋. 蒙卡渲染画面多特征非局部均值滤波降噪算法[J]. 系统仿真学报, 2022, 34(6): 1259-1266.
[7]	周培培, 侯幸林. 一种用于图像融合的无监督深度神经网络[J]. 系统仿真学报, 2022, 34(6): 1267-1274.
[8]	陈麒, 崔昊杨. 基于改进鸽群层级的无人机集群视觉巡检模型[J]. 系统仿真学报, 2022, 34(6): 1275-1285.
[9]	王沐晴, 张磊, 范秀敏, 骆晓萌, 朱文敏. VR外设驱动的虚拟人姿态优化仿真方法[J]. 系统仿真学报, 2022, 34(6): 1296-1303.
[10]	程鹏, 张文柱, 谢书翰, 杨子轩. 基于移动边缘计算的车联网任务卸载研究与仿真[J]. 系统仿真学报, 2022, 34(6): 1304-1311.
[11]	陆承, 靳学胜. 基于Steam VR的交互仿真水枪灭火训练系统设计[J]. 系统仿真学报, 2022, 34(6): 1312-1319.
[12]	高宏鼐, 付丽疆, 夏倩, 郭亚. 可观测度在光合作用模型性能评估中的应用[J]. 系统仿真学报, 2022, 34(6): 1330-1342.
[13]	倪凌佳, 黄晓霞, 李红旮, 张子博. 基于协作式深度强化学习的火灾应急疏散仿真研究[J]. 系统仿真学报, 2022, 34(6): 1353-1366.
[14]	孙一铃, 陈谊, 单桂华, 李晓兴. 基于AR技术的多人互动地球仪系统[J]. 系统仿真学报, 2022, 34(6): 1367-1374.
[15]	蒙盾, 胡卓, 张华军. 基于改进A^*算法的多层邮轮疏散系统仿真[J]. 系统仿真学报, 2022, 34(6): 1375-1382.