Priority Queues

By Lee Killough

Contents

• Introductory Material
• Priority Queue Starting Points
• Papers on Priority Queues
• Priority Queue Implementations
• Topics Related to Priority Queues
• Heap Statistics
• Priority Queues Survey
• About This Page
• Pages which refer to this one
• Glossary

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

• A comparative study of parallel and sequential priority queue algorithms, with Robert Rönngren

Rolf Fagerberg

• A Note on Worst Case Efficient Meldable Priority Queues   Abstract

Douglas W. Jones

• An Empirical Comparison of Priority-Queue and Event-Set Implementations^*   Review

Andrew V. Goldberg

• Buckets, Heaps, Lists, and Monotone Priority Queues, with Boris V. Cherkassky and Craig Silverstein   Abstract   older version   Software
• Heap-on-Top Priority Queues, with Boris V. Cherkassky and Craig Silverstein   Abstract

Anthony LaMarca

• The Influence of Caches on the Performance of Heaps, with Richard E. Ladner   Abstract

Mauricio Marín

• On the Pending Event Set and Binary Tournaments
• An Empirical Comparison of Priority Queue Algorithms

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

• Algorithms From P to NP: Design and Efficiency, pp. 130-187 Software

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

• See Rabin A. Sugumar

Arne Andersson

• See Mikkel Thorup

Mike D. Atkinson

• Priority Queues and Multisets
  • HTML
• Priority Queues and Permutations   Abstract
• Min-max heaps and generalized priority queues^*, with Jörg-Rüdiger Sack Nicola Santoro, Thomas Strothotte   Review

Rassul Ayani   (on leave)

• A comparative study of parallel and sequential priority queue algorithms, with Robert Rönngren   Abstract
• Lazy Queue: A new approach to implementation of the pending-event set, with J. Riboe and Robert Rönngren
• A Comparative Study of Some Priority Queues Suitable For Implementation of the Pending Event Set, with J. Riboe and Robert Rönngren
• Efficient Implementation of Event Sets in Time Warp, with Robert Rönngren, Samir R. Das and Richard M. Fujimoto   Abstract
• LR-algorithm: Concurrent Operations on Priority Queues

Armin Bäumker

• See Friedhelm Meyer auf der Heide

Greg Barnes

• Wait-Free Algorithms for Heaps

Ricardo Baeza-Yates

• See Mauricio Marín

Stacey R. Berkowitz

• See Ben Shaby

Jesper Bojesen

• Heap Implementations and Variations
• Performance Engineering Case Study: Heap Construction, with Maz Spork and Jyrki Juhani Katajainen

Joan Boyar

• See Rolf Fagerberg

J.D. Bright

• See Gregory F. Sullivan

Gerth Stølting Brodal

(for abstracts or related work, refer to publications page)

• Funnel Heap - A Cache Oblivious Priority Queue, with Rolf Fagerberg   Slides
• Worst-Case Efficient External-Memory Priority Queues, with Jyrki Juhani Katajainen   Condensed version
• Comparator Networks for Binary Heap Construction, with Maria Cristina Pinotti   Other Version
• A Parallel Priority Queue with Constant Time Operations, with Christos D. Zaroliagis, Jesper Larsson Träff
  Other versions:
  • A Parallel Priority Data Structure with Applications
  • A Parallel Priority Queue with Constant Update Time MPI Informatik
• Worst Case Efficient Data Structures (thesis)
• The Randomized Complexity of Maintaining the Minimum, with Shiva Chaudhuri, Jaikumar Radhakrishnan
• Optimal Purely Functional Priority Queues with Chris Okasaki   Software
• Priority Queues on Parallel Machines
• Worst-Case Efficient Priority Queues
• Fast Meldable Priority Queues

Mark Robbin Brown

• The analysis of a practical and nearly optimal priority queue Abstract

Randy Brown

• Calendar Queues: A Fast O(1) Priority Queue Implementation For the Simulation Event Set Problem

Robert J. Brown

• An Efficient Algorithm for Very Large Priority Queues

Adam L. Buchsbaum

• Data-Structural Bootstrapping and Catenable Deques (thesis)
• Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues, with Rajamani Sundar and R.E. Tarjan

Svante Carlsson

• See Jingsen Chen

Bernand Chazelle

• The Soft Heap: An Approximate Priority Queue with Optimal Error Rate

Jingsen Chen

• The Complexity of Heaps^*, with Svante Carlsson   Abstract
• An efficient construction algorithm for a class of implicit double-ended priority queues
• Parallel heap construction using multiple selection

Shenfeng Chen

• Using Difficulty of Prediction to Decrease Computation: Fast Sort, Priority Queue and Convex Hull on Entropy Bounded Inputs, with John H. Reif

Boris V. Cherkassky

• See Andrew V. Goldberg

Seonghun Cho, with Sartaj Sahni

• Mergeable Double-Ended Priority Queues   Abstract
• Weight Biased Leftist Trees and Modified Skip Lists   Abstract

Chris Clack

Andreas Crauser

• Efficient Priority Queues in External Memory, with Paolo Ferragina and Ulrich Meyer   Mirror

Van-Dat Cung

• An Efficient Implementation of Parallel A*, with Bertrand Le Cun
• The Outcome of a Know-how: a Branch-and-Bound Library, with Bertrand Le Cun, Catherine Roucairol, Salah Dowaji

Sajal K. Das

• Optimal and Load Balanced Mapping of Parallel Priority Queues in Hypercubes, with Maria Cristina Pinotti and Falguni Sarkar   Abstract
• Distributed Priority Queues on Hypercube Architectures, with Maria Cristina Pinotti and Falguni Sarkar
• Parallel and Distributed Meldable Priority Queues Based on Binomial Heaps, with Maria Cristina Pinotti and Vincenzo A. Crupi

Etienne Deprit

• Parallelism and Locality in Priority Queues, with Szu-Tsung Cheng, Jeff A. Jones, Abhiram Ranade, Sun-Inn Shih   Abstract

Paul F. Dietz

• Heap Construction in the Parallel Comparison Tree Model
• Very Fast Optimal Algorithms for Heap Construction

Yuzheng Ding

• See Mark Allen Weiss

Wolfgang Dittrich

• See Friedhelm Meyer auf der Heide

Brandon Dixon

• Minimum Spanning Tree Verification, Fast Priority Queues, and Massively Parallel Factoring (thesis)

Stefan Edelkamp

• Implementing HEAPSORT with n log n - 0.9n and QUICKSORT with n log n + 0.2n Comparisons, with Patrick Stiegeler
• On the Performance of WEAK-HEAPSORT
• Weak-Heapsort (German) (Thesis)

Rolf Fagerberg

• A Generalization of Binomial Queues   Abstract
• A Note on Worst Case Efficient Meldable Priority Queues   Abstract
• Amortization Results for Chromatic Search Trees, with an Application to Priority Queues, with Kim Larsen and Joan Boyar   Abstract
  • formerly Chromatic Priority Queues   Abstract

Paolo Ferragina

• See Andreas Crauser

Michael J. Fischer

• Fishspear: A Priority Queue Algorithm^*, with Michael S. Paterson   Abstract   Review

Rudolf Fleischer

• A tight lower bound for the worst case of bottom-up-heapsort   Abstract
• A simple balanced search tree with O(1) worst-case update time   Abstract

G.N. Frederickson

Michael L. Fredman

• Pairing Heaps are Suboptimal   Abstract
• On the efficiency of pairing heaps and related data structures^*   Abstract
• Information Theoretic Implications for Pairing Heaps^*
• Fibonacci heaps and their uses in improved network optimization algorithms^*, with R.E. Tarjan   Review

Harold N. Gabow

Alexandros V. Gerbessiotis Publications

• Selection on the Bulk-Synchronous Parallel model with applications to priority queues, with Constantinos J. Siniolakis
• Concurrent Heaps on the BSP model
• Parallel priority queue and list contraction: The BSP approach, with Constantinos J. Siniolakis and Alexandre Tiskin   CAAI version

Andrew V. Goldberg

• Expected Performance of Dijkstra's Shortest Path Algorithm, with R.E. Tarjan   Abstract
• Computational Evaluation of Hot Queues, with Craig Silverstein   Abstract
• Buckets, Heaps, Lists, and Monotone Priority Queues, with Boris V. Cherkassky and Craig Silverstein   older version   Abstract   Software
• Heap-on-Top Priority Queues, with Boris V. Cherkassky and Craig Silverstein   Abstract

Gaston H. Gonnet

J.M. de Graaf

• See Walter A. Kosters

Miltos Grammatikakis

• Priority Queues and Sorting for Parallel Simulation, with Stefan Liesche
  • Was Parallel Priority Queues on Cray T3E   Abstract

Ajay Gupta

• Load Balanced Priority Queues on Distributed Memory Machines

Peter Høyer

• A General Technique for Implementation of Efficient Priority Queues   Condensed version   Review

Xiaobo Hu

• Fast and efficient operations on parallel priority queues, with D.Z. Chen

Timothy C.K. Hui

• Improving the Efficiency of the PES Structure In Discrete Event Simulations (thesis) Industrial report
• FELT: A Far Future Event List Structure Optimized for Calendar Queues

Galen C. Hunt

• See Michael L. Scott

Hsien-Kuei Hwang

• On the number of heaps

Theodore Johnson

• A Highly Concurrent Priority Queue Based on the B-link Tree   Abstract
• A Prioritized Multiprocessor Spin Lock with Krishna Harathi   Abstract

Arne T. Jonassen

• The stationary p-tree forest   Abstract

Douglas W. Jones

• Simulation Pending-Event-Set Implementations
• A generalized hold model^*, with Chien-Chun Chou, Steven C. Bruell, Wen Zhang
• An Empirical Comparison of Priority-Queue and Event-Set Implementations^*   Review
• Concurrent operations on priority queues^*   Review

Rolf Karlsson

Jyrki Juhani Katajainen

• Methodological issues in algorithm experimentation: a case study of heaps
• Performance Engineering Case Study: Heap Construction, with Maz Spork and Jesper Bojesen
• External heaps combined with effective buffering, with Ramzi Fadel, Kim V. Jakobsen, Jukka Teuhola
• Worst-Case Efficient External-Memory Priority Queues, with Gerth Stølting Brodal   Condensed version
• The Ultimate Heapsort

David J. King

• Functional Binomial Queues   Abstract

Jeffrey H. Kingston

• Are Fibonacci Heaps Optimal?, with Diab Abuaiadh

Jochen Könemann

• Radix heaps, an efficient implementation for priority queues, with Christoph Schmitz and Christian Schwarz   Abstract

Walter A. Kosters

• Triangular Heaps, with J.M. de Graaf
• Expected Heights in Heaps, with J.M. de Graaf
• Heap Bibliography

Alan T. Krantz

• Analysis of an efficient algorithm for the hard-sphere problem^*   Abstract

Vipin Kumar

• Concurrent Access of Priority Queues, with V. Nageshwara Rao
• Parallel Processing of Discrete Optimization Problems, with Ananth Y. Grama and Panos M. Pardalos   Abstract
• Parallel Best-First Search of State-Space Graphs: A Summary of Results, with K. Ramesh and V. Nageshwara Rao

Christopher Lee Kuszmaul

• Efficient Merge and Insert Operations for Binary Heaps Abstract

Richard E. Ladner

• See Anthony LaMarca

Anthony LaMarca

• The Influence of Caches on the Performance of Heaps, with Richard E. Ladner   Abstract
• Optimizing Static Calendar Queues, with Richard E. Ladner and K. B. Erickson   Abstract
• The Influence of Caches on the Performance of Sorting, with Richard E. Ladner  
  • Preliminary version

Simon Lam

• See Geoffrey G. Xie

Kim Skak Larsen

• See Rolf Fagerberg

Bertrand Le Cun

• See Van-Dat Cung

Jörg Liebeherr

• Priority Queue Schedulers with Approximate Sorting in Output Buffered Switches, with Dallas Wrege   Abstract

Walter Luh

• A Heap Based Priority Queue, with Edward Li

Bernard Mans

• Portable Distributed Priority Queues with MPI

Mauricio Marín

• Discrete-Event Simulation on the Bulk-Synchronous Parallel Model (thesis)
• An Empirical Assessment of Optimistic PDES on BSP
• Binary Tournaments and Priority Queues: PRAM and BSP
• Direct BSP Algorithms for Parallel Discrete-Event Simulation
• On the Pending Event Set and Binary Tournaments
• An Empirical Comparison of Priority Queue Algorithms
• Priority Queue Operations on EREW-PRAM
• Billiards and Related Systems On The Bulk Synchronous Parallel Model
• Hashing-Cell Combination for Boundless Space Event-Driven Molecular Dynamics
• An Object Oriented C++ Approach for Discrete Event Simulation of Complex and Large Systems of Many Moving Objects
• An Event-Driven Simulation Environmment for Hard Particle Molecular Dynamics
• A New Priority Queue for Simulation of Many Objects, with Ricardo Baeza-Yates and Patricio Cordero   Draft
• Molecular Dynamics and Kinetic Theory Group

Yossi Matias

• Approximate Data Structures with Applications, with Jeffrey S. Vitter and Neal E. Young   Abstract & Thumbnail
• Performance evaluation of approximate priority queues, with Suleyman Cenk Sahinalp and Neal E. Young

Alessandro Mei

• See Alan Bertossi

Friedhelm Meyer auf der Heide

• Priority Queue Operations and Selection for the BSP* Model , with Armin Bäumker, Wolfgang Dittrich, Ingo Rieping   Abstract Euro-Par '96

Ulrich Carsten Meyer

• See Andreas Crauser

Maged M. Michael

• See Michael L. Scott

Simon W. Moore

• Tagged up/down sorter -- A hardware priority queue, with Brian T. Graham   Abstract

Bernard M.E. Moret

• Algorithms From P to NP: Design and Efficiency, with H.D. Shapiro Software

Jainendra K. Navlakha

• The Distribution of Keys In a Binary Heap, with M.A. Weiss
• Finding the k-th largest element in a large heap in O(k log log n) time

Bengt Julio Nilsson

Chris Okasaki

• See Gerth Stølting Brodal

Stephan Olariu

• Optimal Parallel Initialization Algorithm for a Class of Priority Queues, with Zhaofang Wen

Ian Parberry

• Load Sharing With Parallel Priority Queues   Abstract

Srinivasan Parthasarathy

• See Michael L. Scott

Michael S. Paterson

• See M.J. Fischer

Stephane Perez

• Priority Trees

Maria Cristina Pinotti

• See Sajal K. Das

Patricio V. Poblete

Thomas Porter

• Random insertion into a priority queue structure, with Istvan Simon   Abstract

Sushil K. Prasad

• Parallel Heap: A Practical Priority Queue For Fine-to-Medium Grained Applications on Small Multiprocessors, with Sagar I. Sawant

Helmut Prodinger

• Average Case-Analysis of Priority trees: A structure for priority queue administration   Abstract
• Descendants in heap ordered trees or a triumph of computer algebra   Abstract
• The level of nodes in heap ordered trees   Abstract
• Depth and path length of heap ordered trees   Abstract

Rajeev Raman

• Eliminating Amortization: On Data Structures with Guaranteed Response Time

John H. Reif

• See Shenfeng Chen

Ingo Rieping

• See Friedhelm Meyer auf der Heide

Robert Rönngren

• See Rassul Ayani

Jörg-Rüdiger Sack

• See Mike D. Atkinson

Suleyman Cenk Sahinalp

• See Yossi Matias

Sartaj Sahni

• See Seonghun Cho

Nicola Santoro

• See Mike D. Atkinson

Peter Sanders   Old Page

• Fast Priority Queues for Cached Memory   Condensed ALENEX version   Software
• Randomized Priority Queues for Fast Parallel Access   Expanded Version
• Fast priority queues for parallel branch-and-bound
• Flaschenhalsfreie parallele Priority queues

Falguni Sarkar

• See Sajal K. Das

Berry Schoenmakers

• Data Structures and Amortized Complexity in a Functional Setting (thesis)
• A Tight Lower Bound for Top-Down Skew Heaps   Abstract
• A Systematic Analysis of Splaying   Abstract
• Inorder Traversal of a Binary Heap and its Inversion in Optimal Time and Space   Abstract
• The Derivation of a Tighter Bound for Top-Down Skew Heaps, with Anne Kaldewaij   Abstract

Michael L. Scott

• Efficient Algorithm for Concurrent Priority Queue Heaps, with Galen C. Hunt, Maged M. Michael, Srinivasan Parthasarathy   Abstract   Pseudocode
• Simple, fast, and practical non-blocking and blocking concurrent queue algorithms   HTML   Software   ACM Proc. ^*

Ben Shaby

• Unix Scheduler Implemented With a Pairing Heap, with Stacey R. Berkowitz

Henry D. Shapiro

• See Bernard M.E. Moret

Nir Shavit   TOC page

• Scalable Concurrent Priority Queues, with Asaph Zemach

Craig Silverstein

• See Andrew Goldberg

Rahul Simha

• Fast data structures for shortest path routing: a comparative evaluation, with G. Oberhauser

Constantinos J. Siniolakis

• See Alex V. Gerbessiotis

D.D. Sleator

Maz Spork

• Design and Analysis of Cache-Conscious Programs (Thesis)
• Performance Engineering Case Study: Heap Construction, with Jyrki Juhani Katajainen and Jesper Bojesen

John T. Stasko

• Tidy Animations of Tree Algorithms, with Carlton Reid Turner
• Do algorithm animations assist learning?: an empirical study and analysis^*, with Albert Badre and Clayton Lewis   Abstract
• Pairing Heaps: Experiments and Analysis^*, with Jeffrey S. Vitter

Jørgen Staunstrup

• The priority queue as an example of hardware/software codesign, with Niels Mellergaard, Flemming Høeg

Jeffrey S. Steinman

• The SPEEDES Qheap: A Priority-Queue Data Structure
• SPEEDES Introduction
• Discrete-Event Simulation and the Event Horizon^*   Abstract
• Discrete-Event Simulation and the Event Horizon Part 2: Event List Management^*   Abstract
• US5850538: Priority Queues for Computer Simulations

Rabin A. Sugumar

• Efficient Simulation of Multiple Cache Configurations using Binomial Trees, with Santosh G. Abraham

Gregory F. Sullivan

• Checking Mergeable Priority Queues, with J.D. Bright
• On-Line Error Monitoring for Several Data Structures, with J.D. Bright   Abstract

Björn von Sydow

• Dependently typed binomial queues

Tadao Takaoka

• Shortest Path Algorithms for Nearly Acyclic Directed Graphs
• Theory of 2-3 Heaps
• Theory of Trinomial Heaps

R.E. Tarjan   InterTrust

• Design and analysis of a data structure for representing sorted lists, with Mark R. Brown   Abstract

Jukka Teuhola

• See Jyrki Juhani Katajainen

Mikkel Thorup

• Tight(er) Worst-case Bounds on Dynamic Searching and Priority Queues, with Arne Andersson   Abstract
• Faster deterministic sorting and priority queues in linear space   Abstract
• A pragmatic implementation of monotone priority queues, with Arne Andersson
• On RAM Priority Queues
• Equivalence Between Sorting and Priority Queues

Alexandre Tiskin

• See Alex V. Gerbessiotis

Peter van Emde Boas

• An O(n log logn) On-line Algorithm for the Insert-Extract Min Problem   Abstract

Sriranga Veeraraghavan

• A Heap Based Priority Queue

Jeffrey S. Vitter

• See Yossi Matias, John Stasko

Jean E. Vuillemin

• A data structure for manipulating priority queues

Mark Allen Weiss

• The Relaxed Min-Max Heap: A Mergeable Double-Ended Priority Queue, with Y. Ding
• The k-d Heap: An Efficient Multi-Dimensional Priority Queue, with Y. Ding
• The Distribution of Keys In a Binary Heap, with J.K. Navlakha

Mike Wozniewski

• Priority Queues and the van Emde Boas Implementation

Dallas E. Wrege

• See Jörg Liebeherr

Geoffrey G. Xie

• An Efficient Adaptive Search Algorithm for Scheduling Real-Time Traffic, with Simon S. Lam   Abstract

Neal E. Young

• See Yossi Matias

Lixin Yu

• A Survey on Parallel Algorithms for Priority Queues

Rodger Zanny

• Efficiency of Distributed Priority Queues in Parallel Adaptive Integration (Thesis)   Abstract   HTML

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:

• pool.zip (32-bit x86 program)

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(n²) 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:

• Priority queues come in more varieties and styles than most other data structures;
• The Heap Property is weak, yet strong enough for a priority queue's characteristics;
• Priority queues are dynamically changing, and so there's an eternal quality to them :-)

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

• Google
• AltaVista

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).