<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-221

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

M.J. Fischer and M.S. Paterson, Fishspear: A Priority Queue Algorithm (June 1, 1992).

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.

<%@ include file="cited.html" %>

M.J. Fischer and M.S. Paterson, "Fishspear: A Priority Queue Algorithm", Journal of the ACM 41, pp. 3-30 (1994)

<%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>