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

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]	黄涛, 张智, 丁玉杰, 陈艳波, 王晶, 张文倩. 考虑动态频率安全与N-k故障的鲁棒应急调度方法[J]. 系统仿真学报, 2025, 37(12): 2981-2993.
[2]	张润昭, 陈艳波, 黄涛, 田昊欣, 强涂奔, 张智. 基于异构负荷特征解析预测的虚拟电厂调度方法[J]. 系统仿真学报, 2025, 37(12): 2994-3006.
[3]	于祥星, 赵艳东, 张宝琳. 基于电涡流NES的海上风机塔架振动控制[J]. 系统仿真学报, 2025, 37(12): 3007-3017.
[4]	李斌, 王于绰. 基于多策略融合的光伏系统故障诊断方法[J]. 系统仿真学报, 2025, 37(12): 3018-3032.
[5]	李孝斌, 胡冰, 尹超, 李波, 马军. 基于时空图卷积的汽车配件供应链需求预测与仿真分析[J]. 系统仿真学报, 2025, 37(12): 3060-3074.
[6]	彭艺, 雷云揆, 杨青青, 李辉, 王健明. 改进PID搜索算法的山地环境无人机路径规划[J]. 系统仿真学报, 2025, 37(12): 3075-3086.
[7]	伍枢珩, 刘永奎, 张霖, 肖莹莹, 王力翚. 基于改进YOLOv8的轻量级装配工件检测算法[J]. 系统仿真学报, 2025, 37(12): 3099-3111.
[8]	陈逸, 邱思航, 朱正秋, 季雅泰, 赵勇, 鞠儒生. 基于启发式的人-大模型协作寻源方法[J]. 系统仿真学报, 2025, 37(12): 3112-3127.
[9]	任亮, 周泽榕, 马云峰. “货到人”系统订单拣选和分拣协同优化问题[J]. 系统仿真学报, 2025, 37(12): 3128-3139.
[10]	索婧怡, 卢柏宏, 屈澈. 影视LED光源光强分布测定及其在游戏引擎中的仿真研究[J]. 系统仿真学报, 2025, 37(12): 3140-3151.
[11]	龚建兴, 胡海, 任海慧, 吴瑞祥. 面向虚实结合的军事训练系统互操作模型与运用[J]. 系统仿真学报, 2025, 37(12): 3161-3175.
[12]	徐智霞, 王蕊, 孙楠, 何兵, 沈晓卫, 朱晓菲. 基于改进遗传算法的协同干扰资源分配问题研究[J]. 系统仿真学报, 2025, 37(12): 3176-3189.
[13]	刘翔, 金乾坤. 基于PAC-Bayes的多目标强化学习A2C算法研究[J]. 系统仿真学报, 2025, 37(12): 3212-3223.
[14]	杨兰英, 李超, 邹海锋, 万江涛, 张仁强, 刘惠, 卢宏. 基于改进蚁群算法与A*算法相融合的机器人路径规划优化[J]. 系统仿真学报, 2025, 37(11): 2956-2965.
[15]	苏筱婷, 张小威, 田义, 李奇, 王帅豪. 星光导航动态仿真场景时序设计方法研究[J]. 系统仿真学报, 2025, 37(11): 2946-2955.