1.1.2 Priority Queues
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.
Recommended Books
Related Links
Lee Killough's link site for Priority Queues and Heaps
The fxt demos: data structures
Related Problems
This page last modified on 2008-07-10
.
www.algorist.com
Data Structures and Algorithm Analysis in C++ (3rd Edition)
Handbook of Data Structures and Applications
Algorithms in C++: Fundamentals, Data Structures, Sorting, Searching
The Art of Computer Programming: Fundamental Algorithms
