A More Complex Data Structure: Priority Queues

To qualitatively improve the brute-force algorithms so we can have efficient algorithms, we always need to overcome higher-level obstacles. However, the running time of polynomial-time algorithms can often be further improved through the implementation details and use of more complex data structures. Some of those complex data structures are usually specialized for solving some kind of problems, while we can also find others that are more general in their applications. This section illustrates and analyses a broadly used complex data structure, called priority queue. In a priority queue, each element is inserted with a certain key or value, which helps to identify the element for various manipulations. Priority queues perform non-trivial computations when called, and are usually a much better alternative to arrays and lists.