Fishspear: a priority queue algorithm

ABSTRACT

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.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Svante Carlsson, A variant of Heapsort with almost optimal number of comparisons, Information Processing Letters, v.24 n.4, p.247-250, March 1987 [doi>10.1016/0020-0190(87)90142-6]
• 3: Gaston H Gonnet , J Ian Munro, Heaps on heaps, SIAM Journal on Computing, v.15 n.4, p.964-971, Nov. 1986 [doi>10.1137/0215068]
• 4: C. A. R. Hoare, Communicating sequential processes, Communications of the ACM, v.21 n.8, p.666-677, Aug. 1978 [doi>10.1145/359576.359585]
• 5: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 6: Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985 [doi>10.1145/3828.3835]
• 7: Daniel Dominic Sleator , Robert Endre Tarjan, Self adjusting heaps, SIAM Journal on Computing, v.15 n.1, p.52-69, Feb. 1986 [doi>10.1137/0215004]
• 8: ~WILLIAMS, J. W. J. 1964. Algorithm 232: Heapsort. Commun. ACM 7, 6 (June), 347-348.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Lists, stacks, and queues

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Contiguous representations**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching; Computations on discrete structures; Sequencing and scheduling

General Terms:
Algorithms, Design, Theory

Keywords:
comparison count, complexity analysis, heap, online algorithm, priority queue, running time, sequential storage