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 条
  • [1] An efficient algorithm for concurrent priority queue heaps
    Hunt, GC
    Michael, MM
    Parthasarathy, S
    Scott, ML
    INFORMATION PROCESSING LETTERS, 1996, 60 (03) : 151 - 157
  • [2] Fast multidimensional nearest neighbor search algorithm using priority queue
    Ajoka, Shiro
    Tsuge, Satoru
    Shishibori, Masami
    Kita, Kenji
    ELECTRICAL ENGINEERING IN JAPAN, 2008, 164 (03) : 69 - 77
  • [3] PARALLEL HEAP - AN OPTIMAL PARALLEL PRIORITY QUEUE
    DEO, N
    PRASAD, S
    JOURNAL OF SUPERCOMPUTING, 1992, 6 (01): : 87 - 98
  • [4] Priority queue with customer upgrades
    He, Qi-Ming
    Xie, Jingui
    Zhao, Xiaobo
    NAVAL RESEARCH LOGISTICS, 2012, 59 (05) : 362 - 375
  • [5] THE PERMUTATIONAL POWER OF A PRIORITY QUEUE
    ATKINSON, MD
    THIYAGARAJAH, M
    BIT, 1993, 33 (01): : 2 - 6
  • [6] Efficiency of Priority Queue Architectures in FPGA
    Kohutka, Lukas
    JOURNAL OF LOW POWER ELECTRONICS AND APPLICATIONS, 2022, 12 (03)
  • [7] The soft heap: An approximate priority queue with optimal error rate
    Chazelle, B
    JOURNAL OF THE ACM, 2000, 47 (06) : 1012 - 1027
  • [8] ANALYSIS OF A PRIORITY QUEUE WITH BERNOULLI SCHEDULES
    KATAYAMA, T
    TAKAHASHI, Y
    IFIP TRANSACTIONS C-COMMUNICATION SYSTEMS, 1992, 5 : 113 - 131
  • [9] Dynamics of Priority-Queue Networks
    Min, Byung-Joon
    Goh, Kwang-Il
    Kim, In-mook
    COMPLEX SCIENCES, PT 2, 2009, 5 : 2229 - 2231
  • [10] A Lock-Free, Array-Based Priority Queue
    Liu, Yujie
    Spear, Michael
    ACM SIGPLAN NOTICES, 2012, 47 (08) : 323 - 324
12345