Priority Queues

By Lee Killough

If links are broken, please look here for papers. I have not had time to update links.

Contents


Introductory Material

Definitions of Algorithms, Data Structures, and Problems
Definition of priority queue and related terms, in Paul Black's computer science glossary

Heaps (Priority Queues)
Ian Graham's lecture

Heaps
Stefan Xenos' survey of priority queues and their complexities

Data Structures and Algorithms: Queues
John Morris' notes on priority queues

Data Structures
Introduction to data structures, with Java code, by Peter M. Williams

Heaps and Priority Queues
Online chapter of Data Structures and Algorithms with Object-Oriented Design Patterns in C++, by Bruno R. Preiss

Priority Queues and Heapsort
Introduction to heaps using tournaments, by Steven S. Skiena

Priority Queues
Introduction to priority queues, including k-heaps, Leftist heaps, and binomial queues, by Barry Kurtz

Data Structures in C++ Case Study: Priority Queues
Timothy Colburn's lecture slides on priority queues

Priority Queues and Heaps
Introduction to priority queues and heapsort, with C code

The Complete Collection of Algorithm Animations
Pointers to online animations of algorithms and data structures
A Priority Queue Tester
A Java demonstration of priority queue insertion and removal

Starting Points

If you're just looking for the fastest priority queue for an application, or if you want a survey of the different kinds of priority queues and their strengths and weaknesses, I recommend you first read the following:

* Indicates access may be restricted

Rassul Ayani

Rolf Fagerberg

Douglas W. Jones

Andrew V. Goldberg

Anthony LaMarca

Mauricio Marín

Bernard M.E. Moret, H.D. Shapiro


Papers on Priority Queues

Arranged alphabetically by author. Hyperlinks under the authors' names, are links to their personal home pages.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

* Indicates access may be restricted


Santosh G. Abraham

Arne Andersson

Mike D. Atkinson

Rassul Ayani   (on leave)

Armin Bäumker

Greg Barnes

Ricardo Baeza-Yates

Stacey R. Berkowitz

Jesper Bojesen

Joan Boyar

J.D. Bright

Gerth Stølting Brodal
(for abstracts or related work, refer to publications page)
Mark Robbin Brown

Randy Brown

Robert J. Brown

Adam L. Buchsbaum

Svante Carlsson

Bernand Chazelle

Jingsen Chen

Shenfeng Chen

Boris V. Cherkassky

Seonghun Cho, with Sartaj Sahni

Chris Clack

Andreas Crauser

Van-Dat Cung

Sajal K. Das

Etienne Deprit

Paul F. Dietz

Yuzheng Ding

Wolfgang Dittrich

Brandon Dixon

Stefan Edelkamp

Rolf Fagerberg

Paolo Ferragina

Michael J. Fischer

Rudolf Fleischer

G.N. Frederickson

Michael L. Fredman

Harold N. Gabow

Alexandros V. Gerbessiotis Publications

Andrew V. Goldberg

Gaston H. Gonnet

J.M. de Graaf

Miltos Grammatikakis

Ajay Gupta

Peter Høyer

Xiaobo Hu

Timothy C.K. Hui

Galen C. Hunt

Hsien-Kuei Hwang

Theodore Johnson

Arne T. Jonassen

Douglas W. Jones

Rolf Karlsson

Jyrki Juhani Katajainen

David J. King

Jeffrey H. Kingston

Jochen Könemann

Walter A. Kosters

Alan T. Krantz

Vipin Kumar

Christopher Lee Kuszmaul

Richard E. Ladner

Anthony LaMarca

Simon Lam

Kim Skak Larsen

Bertrand Le Cun

Jörg Liebeherr

Walter Luh

Bernard Mans

Mauricio Marín

Yossi Matias

Alessandro Mei

Friedhelm Meyer auf der Heide

Ulrich Carsten Meyer

Maged M. Michael

Simon W. Moore

Bernard M.E. Moret

Jainendra K. Navlakha

Bengt Julio Nilsson

Chris Okasaki

Stephan Olariu

Ian Parberry

Srinivasan Parthasarathy

Michael S. Paterson

Stephane Perez

Maria Cristina Pinotti

Patricio V. Poblete

Thomas Porter

Sushil K. Prasad

Helmut Prodinger

Rajeev Raman

John H. Reif

Ingo Rieping

Robert Rönngren

Jörg-Rüdiger Sack

Suleyman Cenk Sahinalp

Sartaj Sahni

Nicola Santoro

Peter Sanders   Old Page

Falguni Sarkar

Berry Schoenmakers

Michael L. Scott

Ben Shaby

Henry D. Shapiro

Nir Shavit   TOC page

Craig Silverstein

Rahul Simha

Constantinos J. Siniolakis

D.D. Sleator

Maz Spork

John T. Stasko

Jørgen Staunstrup

Jeffrey S. Steinman

Rabin A. Sugumar

Gregory F. Sullivan

Björn von Sydow

Tadao Takaoka

R.E. Tarjan   InterTrust

Jukka Teuhola

Mikkel Thorup

Alexandre Tiskin

Peter van Emde Boas

Sriranga Veeraraghavan

Jeffrey S. Vitter

Jean E. Vuillemin

Mark Allen Weiss

Mike Wozniewski

Dallas E. Wrege

Geoffrey G. Xie

Neal E. Young

Lixin Yu

Rodger Zanny

* Indicates access may be restricted


Implementations

Priority Queues
ANSI C implementation and tutorial, by Georg Kraml

LEDA
Library of Efficient Data Structures and Algorithms

Simulation Pending Event Set Implementations
Doug Jones' splay tree and other priority queue implementations

Selection Algorithms
In Handbook of Algorithms and Data Structures

Memory Structures Library (MemSL) for C and C++
Memory Structures Library (MemSL) for C and C++

SimPack/Sim++ Simulation Toolkit
C++ implementations, as a "starting point" for simulation

Heaps
Peter Sanders' C++ implementation of heaps, with benchmark

The Stony Brook Algorithm Repository
Statement of priority queue problem and links to implementations

Sorting and Searching Experimentarium
C and C++ programs for sorting, including bottom-up heapsort

C++ Boost
C++ implementation of d-heaps, Fibonacci heaps, pairing heaps, and splay heaps

SWAN
Simulator Without A Name, with a C++ implementation of calendar queues

Weak-Heapsort
Weak-Heapsort, by Stefan Edelkamp

Priority Queues and the STL
Heaps, and an application to Huffman coding, by Mark Nelson

Fifth DIMACS Challenge -- Priority Queue Tests
Priority queue tests, with some pointers to implementations

MLIB (DS)
Commercial thread-safe software for data structures, in C and C++

Heap Implementations and Variations
Discussion of several implementations using C++ testing tool Heaplab, by Jesper Bojesen

D.D. Sleator's Splay Trees
Top-down splay tree implementations and technical reports

The AVL Page
Threaded AVL tree library, and pointers to other AVL tree resources, by Ben Pfaff

Mark Allen Weiss' Data Structures in Ada Page
Priority queues in Ada

Scheme implementation using pairing heaps
by Darius Bacon

Treaps
Scheme priority queue code, and some Usenet articles on priority queues, by Oleg Kiselyov

PriorityQueue.m
Mathematica package for destructive priority queues based on a heap

libwayne
Wayne's Little Data Structures and Algorithms Library (in C)

EZDSL
Easy Data Structures Library for Delphi, by Julian Bucknall

Bob++
A library for sequential and parallel search algorithms

Priority Queues and the van Emde Boas Implementation
Introduction to the van Emde Boas implementation, by Mike Wozniewski

Related Topics

One good way to find related pages, is to find ones that refer to this one.

Here are some which deserve to be listed separately:

Navigation
A* search, intelligent path-finding, etc.

Amit's A* Pages
Amit's Thoughts on Path-Finding (and finding the right priority queue)

data@{Codepage}
Links to specialized pages like this one

Collision Simulation

For over a decade, a hobby of mine was to find the most efficient method to simulate colliding balls. It started as a toy. Here is the latest version of my work:

It's a very old program, and it has a poor user-interface, but it's a good illustration of a technique better than O(n2) per step for simulating n bouncing balls.

Related links:

Molecular Dynamics and Kinetic Theory Group

Interactive and Exact Collision Detection for Virtual and Simulated Environments

Impulse based simulation

Discrete Event Systems Simulation

Pending Event Set (PES) Structures for Discrete Event Simulations

Ming C. Lin

Heap Statistics

As an illustration of heaps, here are the most often visted links on this page, arranged by type:

Technical Reports* (including theses)
1521
403 510
377 347 132 280
175 326 250 128 69 95 73 270
146 135 152 244 74 188 56 116 42 46 90 47 50 58 91 96
74 36 70 76 71 34 66 150 57 62 49 111 49 36 16 40 16 37 15 26 44 47 18 44 26 31 35 51 47 70 29 41

Software
3737
1020 897
588 552 807 463
551 495 223 269 347 518 201 184
202 136 108 443 129 2 111 85 78 15 105 369 85 152 11 80
11 97 99





























Personal Home Pages
225
62 201
31 39 33 22
12 20 13 14 22 11 3 11
5 12 11 14 7 8 13 10 6 13 8 5 2 2 4 6
4 5 6 9 3 10 7 10 5 5 5 2 5 9 6 5 5 3 3 10 6 7 4 4 2 1 2 2 1 1 3 4

Other Web Pages
6158
5156 3122
3535 778 3032 133
1707 52 125 179 2342 1856 87 79
1146 1440 48 45 23 41 28 6 122 2070 154 194 3 5 8 56
1 5 1 5 1 36 33 4 4 22 9 2 7 14 3 3 19 7 24 17 2 11 1 1 1







* Technical reports are usually binary files, and some are only available by subscription.


Priority Queues Survey

Is closed.

See results of the survey


About This Page

This page is a reference on Priority Queues, by Lee Killough.

It was started in 1996 when I could find no real good online references on priority queues.

My introduction to priority queues was informal and spontaneous -- as a high school student in the 1980s, playing at home on my then-ultra-slow computer (2 MHz), I wanted to find a fast way to simulate bouncing balls. It wasn't until years later, that I realized that what I had been using in my program, already had a name for it: Priority Queue.

Priority queues are interesting, because:

Most of the referenced papers are available online, by following their title links. A page with help on viewing files.

Links to abstracts are usually provided, if they can be found in HTML or plaintext form.

Unless a priority queue researcher has a home page, or a report that is available online, they are not usually listed. For references to offline reports, see the Heap Bibliography.

This page assumes that the reader has some knowledge of algorithms and data structures. Those without any experience at all, are encouraged to visit the introductory section.

This page is one of the growing number of Theory Repositories On the Web, pages which single-mindedly explore a particular subject.

For information on Queueing Theory, which is the study of waiting lines, and which is more about processes and phenomena than about data structures, see Myron Hlynka's Queueing Theory Page.

For information about dynamic memory allocation (whose storage area is often misleadingly called a "heap"), see Benjamin Zorn's Dynamic Storage Allocation and Memory Management Information Repository.

Reports with more than one author are usually listed under the author who has a home page, or the author with the most publications relating to priority queues. Although links to each report could be listed under every coauthor, they aren't, since this would involve a lot of unnecessary duplication.

Items with * after them are usually only available to subscribers of the publication they are published in.

To find new reports on priority queues, I recommend doing a search on CiteSeer, or one of the search engines listed in this directory.

(FermiVista! and Cora used to be my favorites, but they seem to have disappeared.)

For researchers' homepages, see HPSearch.

Why are external links put through a CGI redirection program? Because it allows the collection of statistics on which links are actually visited. It is intended to improve this page, by finding out which links are important and providing them in an illustrative way, not to spy on visitors. (In fact, this page goes out of its way to alert potential victims of Spyware, by detecting it based on browser type, and redirecting the user to information about it.)

I'm sorry, but I don't have the time to update this page much anymore.


Pages which refer to this one

Select a search engine:

Glossary

DecreaseKey (IncreaseKey)
Increase the priority of an arbitrary pointed-to item, by decreasing (increasing) the value of its key.

Delete
Delete an arbitrary pointed-to item from the priority queue.

DeleteMin (DeleteMax)
Find and remove the minimum (or maxmium) keyed item in the priority queue.

FindMin (FindMax)
Find, but do not remove, the minimum (or maximum) keyed item in the priority queue.

Heap
A tree data structure in which every node's key is no larger (or no smaller) than its children's. The root node is a node with the smallest (or largest) key.

Heapify
Transform an arbitrary array of items into a heap. Usually more efficient than simply inserting items one at a time, hence the separate category.

Insert
Add an item to the priority queue.

Meld
Join two priority queues into a larger one. Often the basis for Insert.

Priority Queue
An abstract data type which efficiently keeps track of the item with the highest priority across a series of operations. The basic operations are: Insert, FindMin (or FindMax), and DeleteMin (or DeleteMax). Some implementations also efficiently support joining two priority queues (Meld), deleting an arbitrary item (Delete), and increasing the priority of an item (DecreaseKey or IncreaseKey).


© 2003 Lee Killough