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

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]. 系统仿真学报, 2026, 38(5): 1129-1145.
[2]	李校男, 晁涛, 马萍, 杨明, 王玉轩. 基于期望最大化方法的非线性SSM黑箱鲁棒辨识[J]. 系统仿真学报, 2026, 38(5): 1146-1158.
[3]	刘银钢, 马明, 张荣华. 基于大语言模型的兵棋推演动态任务规划[J]. 系统仿真学报, 2026, 38(5): 1187-1204.
[4]	苏泓嘉, 张成, 刘飞. 基于模糊功能依赖网分析的体系效能评估方法[J]. 系统仿真学报, 2026, 38(5): 1224-1238.
[5]	梅华威, 杨鹏慧, 余洋. 计及数据漂移改进PatchTST的超短期光伏功率预测[J]. 系统仿真学报, 2026, 38(5): 1239-1254.
[6]	李权, 苏鹏, 万海英, 张承玺, 何志坚, 倪艺洋, 赵忠盖, 刘飞. 基于多阶段LHS-EPRCC方法的青霉素发酵过程建模[J]. 系统仿真学报, 2026, 38(5): 1255-1276.
[7]	周子聪, 曾俊杰, 胡越, 朱正秋, 尹全军. 基于次优示例引导的兵棋推演多智能体强化学习方法[J]. 系统仿真学报, 2026, 38(5): 1277-1289.
[8]	石敏, 郭诗盛, 王素琴, 李兆歆, 朱登明. 融合物理与几何先验的无抓取标注6-DoF抓取检测方法[J]. 系统仿真学报, 2026, 38(5): 1290-1302.
[9]	姜彦吉, 肖星佚, 董浩, 于淼, 黄金山, 刘大千, 费博雯. 融合点线特征的图关系优化3D车道线检测方法[J]. 系统仿真学报, 2026, 38(5): 1303-1319.
[10]	张鑫, 张平, 张琛, 刘威, 韩博阳. 非均质土壤条件下挖掘阻力计算模型研究[J]. 系统仿真学报, 2026, 38(5): 1320-1332.
[11]	陶冶, 汤锦辉, 周臣, 王冲. 基于图像表征与特征协同感知的航迹补全方法研究[J]. 系统仿真学报, 2026, 38(5): 1333-1349.
[12]	王伟, 刘东, 崔新豪, 李博, 肖依永, 任羿. 复杂项目多级动态挣值管理数字化模型及应用[J]. 系统仿真学报, 2026, 38(5): 1350-1364.
[13]	彭莉峻, 苏庭琪, 刘沛津, 何林, 周协武, 张闽心. 融合人体关键点的实验室PPE规范穿戴检测方法[J]. 系统仿真学报, 2026, 38(5): 1365-1382.
[14]	滕靖, 童文聪, 张中杰, 姚幸, 李君羡. 有轨电车交叉口速度自动引导方法及仿真评价[J]. 系统仿真学报, 2026, 38(5): 1426-1439.
[15]	范双豪, 何芳, 赵建伟, 胡豪杰, 朱丰超, 李向阳. 基于窗口重构协同表示的高光谱异常检测算法[J]. 系统仿真学报, 2026, 38(5): 1440-1452.