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.

To implement a priority queue using:

• lists: We can have a pointer for the Min of the elements and use it to access the Min and adding elements become easy.
  • Problem: Extraction of Min is hard since it would take us O(n) to update the Min pointer
• The issue may be resolved by storing the elements in a sorted list.
  • Problem: If we use a doubly-linked list, we may need O(n) time to search for where to insert the element and then add it in O(n) time.
  • If we choose to use an array,we would find the position in O(logn) time but we would have to shift all of the other elements one position to the right,which takes up to O(n) time

The heap comes in as a solution to these issues, as it combines the benefits of a sorted array and a list. Elements in a heap order are arranged in such a way the key of any parent element is not bigger than the key of any of its children.