Priority Queues1.3. Structure Choices for Implementing Priority Queues

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, the 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. Now what happens? Of course, this is dynamic. So, while some jobs are running, other new jobs may arrive. So, each time when new jobs arrive they will come with different priorities, and this is the job of the scheduler to make sure that the new jobs with higher priority come ahead of older jobs with lower priority.

A priority queue is a data structure that allows us to manage a collection of jobs, where each job has a priority associated with it. The job scheduler picks the highest priority job to execute next. If a new job arrives while the processor is busy, and it has a higher priority than the currently running job, it should be executed sooner. This requires a dynamic management of the job list based on their priorities, so that the highest priority job can always be processed first. This efficient management is crucial in systems like operating systems, where jobs of varying importance compete for processing time.

Imagine a restaurant where customers have reservations. Customers with higher reservation priorities are seated first. However, if a VIP guest arrives unexpectedly, the manager will ensure they are seated before others, regardless of their reservation time. The order in which customers are served reflects how a priority queue works.

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. The main operation is delete max; delete the maximum priority item from the queue. And then there is an insert. So, a job will come, it will be inserted, and it will come with a priority. So, we need to insert into the list so that subsequent delete max can take this one into account.

The two key functions of a priority queue are 'insert' and 'delete max'. The 'insert' function allows adding a new job with a specified priority. The 'delete max' function removes the job with the highest priority from the queue. Handling these operations efficiently is vital for performance, especially in scenarios with a dynamic flow of tasks that vary in importance.

Think of a digital ticketing system at a concert. When people buy tickets, they are added to the queue based on their type (VIP, regular, etc.). When the event starts, tickets of higher priority (like VIP tickets) are processed first, allowing those attendees to enter the venue before everyone else.

The first solution that one could think of to keep such 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 appending to the list. Insertion is a constant time operation takes time O(1), but if we have an unsorted list, then we have to scan the entire list to find the minimum or the maximum. So, in this case, if we want to do a delete max from an unsorted list, this operation is going to take linear time proportional to the size of the list or the number of jobs pending at the moment.

Using a linear structure like an unsorted list can be simple, but it comes with trade-offs. Insertion is fast since jobs can be appended easily, but finding the job with the highest priority (delete max) requires scanning the entire list, resulting in slow performance (O(N) time). If the list were sorted, delete max would be faster, but inserting jobs would then take longer (also O(N)). This means that both methods face bottlenecks, making them inefficient for a lot of jobs.

Imagine a library where new books are added to a shelf without any order. While it’s quick to place a new book at the end of the shelf, finding the oldest book (to lend out) requires checking each book one by one. Conversely, if books are sorted by year of publication, you can quickly find the oldest book but it takes longer to insert a new one in the correct order.

So, we have to go from a one-dimensional structure to a two-dimensional structure. Here we assume that we know in advance about the total number of jobs we can have. We reorganize this list as a squared array of 5 by 5. So, now you can see here an example of such a thing. Each row is in ascending order. So, now suppose you want to insert a new job into this list. The strategy is very simple; we want to insert it in the correct place in the first row that has free space.

By organizing data in a two-dimensional array rather than a linear list, we can improve the efficiency of both insertion and deletion operations. Each row can be sorted, allowing the maximum element to be quickly identified at the end of each row, which speeds up the delete max operation. Inserting jobs involves finding the correct row and position efficiently, which can significantly reduce the average time complexity compared to a linear structure.

Imagine a library that instead of having a single shelf (linear), has a grid of sections (two-dimensional). Each section is organized and you can quickly find one based on its category and author. It is still necessary to find an empty spot in the right section, but you won’t have to look through the entire library.

So, we have now 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.

Using a two-dimensional array structure reduces the time complexities of both insertion and deletion to O(√N), drastically improving our overall capability to handle N jobs from O(N²) to O(N√N). This efficiency gain showcases the importance of choosing the right data structure for operations concerning dynamic datasets.

Think of a factory assembly line operating more smoothly with an organized setup allowing quick access to products. Instead of searching through piles of items, employees can quickly retrieve what they need, significantly boosting productivity.

Of course, we are not going to be happy with this, others you would have just stop with this. So, we can actually do much better than N to 3 by 2, and this is what we are going to discuss in a later lecture. We will maintain it not in a simple array or a square matrix but in a special kind of binary tree called a heap.

The goal is to improve further by introducing a data structure known as a heap, which organizes data in a binary tree format. This structure balances itself to ensure operations like insert and delete max can happen in logarithmic time (O(log N)), which is more efficient than the previous methods discussed.

Imagine a managing committee of a community where members can vote for issues needing attention. Instead of having people line up to voice their opinions in a disorderly fashion, the committee uses a voting tree to efficiently streamline the process, ensuring that the most critical issues are dealt with promptly and fairly.

--