Priority Queues

A priority queue is a data structure similar to a regular queue, but where each element also has a priority associated with it. In our priority queue, an element with low priority is served before an element with high priority – though this can go either way.

In some implementations, if two elements have the same priority, they're served according to the order in which they were added, while in other implementations, the ordering of elements with the same priority is undefined.

A well-designed priority queue can have insert and pop methods with a time complexity of O(log(n)). As we saw in chapter 1, these kinds of fast priority queues can speed up algorithms like Dijkstra's.