Efficient Priority Queue Constructed on Heap-like Data Structure

doi:10.16182/j.issn1004731x.joss.201701013

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

CLC Number:

TP391

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

References

[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.