Fischer, Michael J. and Paterson, Michael S. (1992) Fishspear : a priority queue algorithm. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
Preview |
PDF (Department of Computer Science Research Report)
WRAP_cs-rr-221.pdf - Other - Requires a PDF viewer. Download (14MB) | Preview |
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.
| Item Type: | Report |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science |
| Library of Congress Subject Headings (LCSH): | Queuing theory, Data structures (Computer science) |
| Series Name: | Department of Computer Science research report |
| Publisher: | University of Warwick. Department of Computer Science |
| Official Date: | June 1992 |
| Dates: | Date Event June 1992 Completion |
| Number: | Number 221 |
| Number of Pages: | 32 |
| DOI: | CS-RR-221 |
| Institution: | University of Warwick |
| Theses Department: | Department of Computer Science |
| Status: | Not Peer Reviewed |
| Publication Status: | Unpublished |
| Re-use Statement: | M.J. Fischer and M.S. Paterson, “Fishspear: A Priority Queue Algorithm”, <i>Journal of the ACM</i> <b>41</b>, pp. 3-30 (1994) |
| Funder: | United States. Office of Naval Research, National Science Foundation (U.S.) (NSF), European Strategic Programme of Research and Development in Information Technology (ESPRIT), Science and Engineering Research Council (Great Britain) (SERC) |
| Grant number: | N00014-82-K-0154 (ONR), N00014-89-J-1980 (ONR), MCS-8116678 (NSF), MCS-8405478 (NSF), IRI-9015570 (NSF), 3075 (ESPRIT), 7141 (ESPRIT) |
| Version or Related Resource: | Fischer, M.J. and Paterson, M.S. (1994). Fishspear: a priority queue algorithm. Journal of the ACM, 41(1), pp. 3-30. |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/60910/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |