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.

The best books available for this problem are Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching by Robert Sedgewick and The Art of Computer Programming : Fundamental Algorithms by Donald Knuth.


Implementations

  • Weisses Data Structure (ADA) (rating 9)
  • LEDA - A Library of Efficient Data Types and Algorithms (C++) (rating 9)
  • SimPack/Sim++ Simulation Toolkit (C++) (rating 7)
  • Handbook of Algorithms and Data Structures (Pascal) (rating 7)
  • Xtango and Polka Algorithm Animation Systems (C++) (rating 4)
  • Netlib / TOMS -- Collected Algorithms of the ACM (FORTRAN) (rating 3)
  • Moret and Shapiro's Algorithms P to NP (Pascal) (rating 3)
  • The Stanford GraphBase (C) (rating 2)
  • RAPID - Robust and Accurate Polygon Interface detection (FORTRAN) (rating 1)

    Related Problems

  • Dictionaries
  • Median and Selection
  • Shortest Path
  • Sorting


    Previous Problem Next Problem

    View the graph for this file

    Bulletin Board
    About ``The Algorithm Design Manual''.
    Send us Mail
    The Stony Brook Algorithm Repository -- go to front page

    This page last modified on Wed Mar 07, 2001 .