Solutions

Here are the solutions for the above problem-solving sections.

45. Priority queue

A priority queue is an abstract data type whose elements have a priority attached to them. Instead of working as a first-in-first-out container, a priority queue makes elements available in the order of their priority. This data structure is used in algorithms such as Dijkstra's shortest path, Prim's algorithm, heap sort, the A* search algorithm, in Huffman codes used for data compression, and others.

A very simple approach to implement a priority queue would be to use an std::vector as the underlying container of elements and always maintain it sorted. That means the maximum and minimum elements are always at the two ends. However, this approach does not provide the most efficient operations.

The most suitable data structure that can be used to implement a priority queue is a heap. This is a tree-based data structure that satisfies the following property: if P is a parent node of C, then the key (the...