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 条

[31] Smart priority queue algorithms for self-optimizing event storage
Bahr, HA
DeMara, RF
SIMULATION MODELLING PRACTICE AND THEORY, 2004, 12 (01) : 15 - 40
[32] Physician scheduling for outpatient department with nonhomogeneous patient arrival and priority queue
Na Li
Xiaorui Li
Paul Forero
Flexible Services and Manufacturing Journal, 2022, 34 : 879 - 915
[33] A Two-Stage M/G/1 Queue with Discretionary Priority
Lian, Zhaotong
Zhao, Ning
2011 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2011, : 1402 - 1406
[34] The Lock-Free k-LSM Relaxed Priority Queue
Wimmer, Martin
Gruber, Jakob
Traeff, Jesper Larsson
Tsigas, Philippas
ACM SIGPLAN NOTICES, 2015, 50 (08) : 277 - 278
[35] Physician scheduling for outpatient department with nonhomogeneous patient arrival and priority queue
Li, Na
Li, Xiaorui
Forero, Paul
FLEXIBLE SERVICES AND MANUFACTURING JOURNAL, 2022, 34 (04) : 879 - 915
[36] Heavy Traffic Response Times for a Priority Queue with Non-linear Priorities
S. S. Mishra
OPSEARCH, 2000, 37 (3) : 252 - 258
[37] A Novel Hardware-Accelerated Priority Queue for Real-Time Systems
Kohutka, Lukas
Nagy, Lukas
Stopjakova, Viera
2018 21ST EUROMICRO CONFERENCE ON DIGITAL SYSTEM DESIGN (DSD 2018), 2018, : 46 - 53
[38] A complexity O(1) priority queue for event driven molecular dynamics simulations
Paul, Gerald
JOURNAL OF COMPUTATIONAL PHYSICS, 2007, 221 (02) : 615 - 625
[39] A Fast Systolic Priority Queue Architecture for a Flow-Based Traffic Manager
Benacer, Imad
Boyer, Francois-Raymond
Belanger, Normand
Savaria, Yvon
2016 14TH IEEE INTERNATIONAL NEW CIRCUITS AND SYSTEMS CONFERENCE (NEWCAS), 2016,
[40] An optimal cache-oblivious priority queue and its application to graph algorithms
Arge, Lars
Bender, Michael A.
Demaine, Erik D.
Holland-Minkley, Bryan
Munro, J. Ian
SIAM JOURNAL ON COMPUTING, 2007, 36 (06) : 1672 - 1695

← 1 2 3 4 5 →