Priority Queues1. Priority Queues

So, we have seen how the use of a clever data structure, the union find data structure can make Kruskal's algorithm more efficient. The other two algorithms which we need to make efficient are Dijkstra's algorithm for the single source shortest path, and Prim's algorithm for the minimum spanning tree. Both of them it turns out required a data structure that is usually called a priority queue.

In this introduction, the importance of priority queues is outlined. They are essential for optimizing certain algorithms in computer science, specifically Kruskal’s, Dijkstra’s, and Prim’s algorithms. These algorithms deal with efficiently processing tasks that have varying levels of importance or priority. The priority queue helps in selecting the task with the highest urgency.

Think of a priority queue like a hospital emergency room. Patients are treated based on the severity of their conditions rather than the order they arrive. Critical patients receive attention first, while those with less urgent needs wait.

So, to understand priority queues, let us look at the following scenario. So, supposing we would have a job scheduler running on an operating system. So, when we run multiple tasks on an operating system each of them runs for a little bit of time, and then is opted out. So, job scheduler maintains a list of all jobs which are pending along with their priorities. Whenever the processor is free, the scheduler picks out a job with a maximum priority in the list and schedules it.

This chunk introduces a practical scenario to understand priority queues better. It describes how a job scheduler operates in an operating system, managing tasks that have different priorities. When the CPU is free, the scheduler selects and executes the job with the highest priority from the list of pending tasks.

Imagine you're at a restaurant with a variety of dishes on the menu. The chef prepares the most popular and ordered items first, ensuring that the best-sellers get served quickly while less popular dishes wait in line.

So, we have two basic operations in a priority queue; the first is to extract the next job which in this case means take the job with the highest priority, and remove it from the queue. Now of course, we have the situation where you have multiple jobs in the same priority. So, we do not assume the priorities are unique, but if they are not unique then we can assume either there is some type writing rule or we do not care which one of the highest priority jobs we get.

In a priority queue, there are primarily two operations: 'delete max' to remove the job with the highest priority, and 'insert' to add a new job with its respective priority. The system must handle scenarios where multiple jobs share the same priority. It can use subsequent rules to decide which job to execute first.

Consider a busy airport where flights have different departure times. If two flights are scheduled to take off at the same time, the airport operations staff may prioritize based on the flight's destination or airline, similar to how the priority queue decides which job to execute.

The first solution that one could think of to keep such a data is to maintain a list, some kind of a linear structure and array or a list, since it is growing dynamically a list is your obvious choice. Now if we keep an unsorted list, then it is easy to add a job, which is up to appended to the list. So, insertion is a constant time operation takes time O(1), but as we have seen many times if we have an unsorted list, then we have to scan the entire list to find the minimum or the maximum.

This section discusses the difficulties faced when using basic data structures like unsorted and sorted lists for priority queues. In an unsorted list, inserting jobs is quick, but finding and removing the highest priority job takes longer. Conversely, a sorted list makes removing the highest priority job quick, but inserting new jobs becomes slower, resulting in inefficiencies.

Imagine a stack of papers (unsorted list) on your desk where you can quickly add new papers. However, when you need to find the most critical document, you have to sift through the entire pile. In contrast, if your documents are neatly organized (sorted list), finding the most critical one becomes easy, but adding a new document means you have to find the right spot in the order, which takes time.

So, we have to go from a one-dimensional structure to a two-dimensional structure. So, let us start with a very naive two-dimensional structure, just to show how we can get drastic improvements, just by moving from one dimension to two dimensions.

This chunk introduces the idea of transitioning from a simple one-dimensional structure (like a list) to a two-dimensional array to improve efficiency in managing a priority queue. The concept of organizing jobs within a grid-like structure allows for better performance during insertion and deletion operations.

Think of a two-dimensional structure as a filing cabinet with several drawers. Each drawer holds specific categories of files. When you need to file a document, you first check which drawer has space, then decide where to place it. This is faster than searching through one large pile of papers.

So, now we have achieved a data structure, which keeps track of elements in a priority queue where insert takes order root N time, delete max takes order root N time, and therefore, now processing a sequence of N jobs takes N root N time. Remember that previously it was order N square.

This part outlines the efficiency gained by using the two-dimensional structure. Both insert and delete-max operations can be performed in square-root N time, resulting in a significant overall time reduction for processing multiple jobs. This contrasts strongly with the O(N^2) time complexity of the linear structures.

If earlier you were sorting through a stack of documents one by one (O(N^2) time), now you’re using a system that categorizes them into drawers, allowing you to access and file documents faster (O(N√N) time).

So, we can actually do much better than N to the power of 3 by 2, and this is what we are going to discuss in a later lecture.

This chunk gives a preview of advanced techniques to manage priority queues even more efficiently, suggesting they will explore a data structure known as a heap. Using a heap will enable both insert and delete-max operations to function in logarithmic time, making the overall processing time even faster.

Think of upgrading your filing system from a cabinet to a digital organizer that automatically sorts and retrieves your documents in mere fractions of a second. This move not only saves time but also scales better with a growing collection of documents as compared to the physical system.

--