Fishspear: A Priority Queue Algorithm (Extended Abstract).

Abstract

The Fishspear priority algorithm is presented and analyzed. Fishspear makes fewer than 80% as many comparisons as heaps in the worst case, and its relative performance is even better in many common situations. The code itself embodies an unusual recursive structure which permits highly dynamic and data-dependent execution. Fishspear also differs from heaps in that it can be implemented efficiently using sequential storage such as stacks or tapes, making it possibly attractive for implementation of very large queues on paged memory systems. (Details of the implementation are deferred to the full paper.)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1983
Accession Number
ADA146580

Entities

People

  • M. J. Fischer
  • M. S. Paterson

Organizations

  • Yale University

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Combinatorial Analysis
  • Computations
  • Computer Science
  • Computers
  • Contracts
  • Equations
  • Intervals
  • Mathematics
  • Military Research
  • Program Management
  • Sequences
  • Technical Information Centers
  • Trees (Data Structures)
  • Universities

Readers

  • Parallel and Distributed Computing.
  • Systems Analysis and Design
  • Thermal Physics or Thermal Science.