C++ High Performance

Priority queues

A priority queue offers constant time lookup of the element with the highest priority. The priority is defined using the less than operator of the elements. Insert and delete both run in logarithmic time. A priority queue is a partially ordered data structure, and it might not be obvious when to use it instead of a completely sorted data structure, for example, a tree or a sorted vector. But in some cases, a priority queue can offer you the functionality you need, and for a lower cost than a completely sorted container.

The Standard Library already provides a partial sort algorithm, so we don't need to write our own. But let's see how we can implement a partial sort algorithm using a priority queue. Suppose we are writing ...