The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.1.2 Priority Queues

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: A set of records with numerical or otherwise totally ordered keys.

Problem: Build and maintain a data structures for quickly inserting and deleting records, while maintaining quick access to the smallest or largest key in the set.

Excerpt from The Algorithm Design Manual: Priority queues are useful data structures in simulations, particularly for maintaining a set of future events ordered by time so that we can quickly retrieve what the next thing to happen is. They are called ``priority'' queues because they enable you to retrieve items not by the insertion time (as in a stack or queue), nor by a key match (as in a dictionary), but by which item has the highest priority of retrieval.

If your application performs no insertions after the first query, there is no need for an explicit priority queue. Simply sort the records by priority and proceed from top to bottom, maintaining a pointer to the last record deleted. This situation occurs in Kruskal's minimum spanning tree algorithm, or when simulating a completely scripted set of events.

However, if you are mixing insertions, deletions, and queries, you need a real priority queue.


Implementations

  • Standard Template library in C++ form SGI (C++) (rating 10)
  • Weisses Data Structure (C++,C,Java,ADA) (rating 9)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 9)
  • JDSL: Java Data Structures Libary (Java) (rating 9)
  • Fast Priority Queues for Cached Memory (C++) (rating 8)
  • GNU Classpath: an GNU Java API Library (Java) (rating 8)

  • Recommended Books

    Data Structures and Algorithm Analysis in C++ (3rd Edition) by Mark Allen Weiss Handbook of Data Structures and Applications by D. Mehta and S. Sahni Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching by Robert Sedgewick
    The Art of Computer Programming: Fundamental Algorithms by Donald Knuth

    Related Links

  • Lee Killough's link site for Priority Queues and Heaps
  • The fxt demos: data structures

    Related Problems


      
    Dictionaries
      
    Median and Selection
      
    Shortest Path
      
    Sorting



    This page last modified on 2008-07-10 .
    www.algorist.com