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.

The following are situations where we may need to use priority queues:

• The Stable Matching Problem: The set of free men is dynamically changing, and the priority queue will help us maintain this set in a much more efficient way.
• Managing real-time events: For instance the scheduling of processes on a computer,where each process has a priority;but processes don't arrive in order of their priority and our goal is to select the one with the currently highest priority and run it.
• Sorting n elements in O(nlogn) time.