FISHSPEAR - A PRIORITY QUEUE ALGORITHM

被引：9

作者：

FISCHER, MJ ^{[1
]}

PATERSON, MS ^{[1
]}

机构：

[1] UNIV WARWICK,DEPT COMP SCI,COVENTRY CV4 7AL,W MIDLANDS,ENGLAND

来源：

JOURNAL OF THE ACM | 1994年 / 41卷 / 01期

关键词：

COMPARISON COUNT; COMPLEXITY ANALYSIS; HEAP; ONLINE ALGORITHM; PRIORITY QUEUE; RUNNING TIME; SEQUENTIAL STORAGE;

D O I：

10.1145/174644.174645

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs from the heap method in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it potentially attractive for implementation of very large queues on paged memory systems.

引用

页码：3 / 30

页数：28

共 50 条

[21] A VLSI PRIORITY PACKET QUEUE WITH INHERITANCE AND OVERWRITE
PICKER, D
FELLMAN, RD
IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS, 1995, 3 (02) : 245 - 253
[22] Performance analysis of the priority queue buffer management mechanism
Jiang, Hong-an
Wang, Xia
PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON COMPUTER, NETWORKS AND COMMUNICATION ENGINEERING (ICCNCE 2013), 2013, 30 : 26 - 28
[23] Sorting Algorithms as Special Cases of a Priority Queue Sort
Bell, Tim
Aspvall, Bengt
SIGCSE 11: PROCEEDINGS OF THE 42ND ACM TECHNICAL SYMPOSIUM ON COMPUTER SCIENCE EDUCATION, 2011, : 123 - 128
[24] Stream-based modelling of an interactive priority queue
Dosch, W
IASTED: PROCEEDINGS OF THE IASTED INTERNATIONAL CONFERENCE ON MODELLING AND SIMULATION, 2003, : 559 - 565
[25] CBPQ: High Performance Lock-Free Priority Queue
Braginsky, Anastasia
Cohen, Nachshon
Petrank, Erez
EURO-PAR 2016: PARALLEL PROCESSING, 2016, 9833 : 460 - 474
[26] Performance analysis of a priority queue: Expedited Forwarding PHB in DiffServ
Demoor, Thomas
Walraevens, Joris
Fiems, Dieter
Bruneel, Herwig
AEU-INTERNATIONAL JOURNAL OF ELECTRONICS AND COMMUNICATIONS, 2011, 65 (03) : 190 - 197
[27] A scalable priority queue architecture for high speed network processing
Zhuang, Xiaotong
Pande, Santosh
25TH IEEE INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS, VOLS 1-7, PROCEEDINGS IEEE INFOCOM 2006, 2006, : 616 - 627
[28] A Priority Queue Model of Human Dynamics with Bursty Input Tasks
Kim, Jin Seop
Masuda, Naoki
Kahng, Byungnam
COMPLEX SCIENCES, PT 2, 2009, 5 : 2402 - +
[29] BGPQ: A Heap-Based Priority Queue Design for GPUs
Chen, Yanhao
Hua, Fei
Jin, Yuwei
Zhang, Eddy Z.
50TH INTERNATIONAL CONFERENCE ON PARALLEL PROCESSING, 2021,
[30] Symmetric Min-Max heap: A simpler data structure for double-ended priority queue
Arvind, A
Rangan, CP
INFORMATION PROCESSING LETTERS, 1999, 69 (04) : 197 - 199

← 1 2 3 4 5 →