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

libstdc++ (rating 10)	OpenJDK 10 (rating 10)
Python Standard Library (rating 10)	Go Standard Library (rating 10)
C++ STL (rating 10)	LEDA (rating 9)
JDSL (rating 9)	Fibonacci Heap (rating 8)
Fast Priority Queues for Cached Memory (rating 8)	Java Collections (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 Problems

Dictionaries	Median and Selection	Shortest Path
Sorting