 |
 |
|
|
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.
  Dictionaries |
  Median and Selection |
  Shortest Path |
  Sorting |
As an Amazon affiliate, I earn from qualifying purchases if you buy from links on this website.
.jpg)
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