Priority Queue

# CHAPTER 15

Priority Queue #

1. Introduction #

2. Learning Objectives #

• Differentiate between a Standard Queue (FIFO) and a Priority Queue.

• Understand how Priority Values dictate the dequeue() order.

• Identify the severe performance flaws of using Arrays/Lists for Priority Queues.

• Understand the theoretical introduction to the Binary Heap (the ultimate Priority structure).

3. The Rules of Priority #

1. 1. The Value (e.g., "Patient: John Doe", or "Task: Print Document").

1. 2. The Priority Weight (e.g., Level 1 Urgency, Level 5 Urgency).

The Dequeue Rule: When dequeue() is called, the structure searches for the element with the *highest priority* and removes it. If two elements share the exact same priority level, it defaults back to standard FIFO (whoever arrived first wins).

*(Note: Depending on the system design, sometimes a lower number means higher priority. For example, Priority 1 is a severe emergency, while Priority 5 is a background task).*

4. Implementation 1: The Naive Array/List #

Method A: Unsorted Array

• enqueue(): Just drop the item at the end of the array. O(1) Time.

• dequeue(): You must run a for loop through the *entire* array to find the item with the highest priority number, and then shift all array elements to remove it. O(n) Time.

Method B: Sorted Linked List

• enqueue(): You must traverse the list to find exactly where to insert the new item so the list stays perfectly sorted by priority. O(n) Time.

• dequeue(): Just pop the Head of the list (since the highest priority is already sorted to the front). O(1) Time.

*The Problem:* Both of these basic implementations force at least one operation to be a painfully slow O(n). In an OS processing millions of CPU tasks, O(n) is unacceptably slow.

5. Implementation 2: The Binary Heap (The Golden Standard) #

By using a Heap, a Priority Queue achieves mathematical brilliance:

• Enqueue: O(log n)

• Dequeue: O(log n)

*(O(log n) is exponentially faster than O(n). If there are 1 million tasks in line, an Array takes 1,000,000 steps to find the highest priority. A Heap takes roughly 20 steps!)*

6. Using a Priority Queue in Code #

// Java Example: Utilizing the built-in PriorityQueue
import java.util.PriorityQueue;
import java.util.Collections;

public class ERSystem {
    public static void main(String[] args) {
        // By default, Java processes the smallest number first (Min-Heap).
        // Let's reverse it so the highest number gets highest priority (Max-Heap)
        PriorityQueue<Integer> erQueue = new PriorityQueue<>(Collections.reverseOrder());

        // enqueue() - Adding patients with priority severity (1-10)
        erQueue.add(3); // Minor cut
        erQueue.add(10); // Heart attack!
        erQueue.add(5); // Broken arm
        
        // Even though 10 was added SECOND, it jumps the line!
        System.out.println("Treating Patient Level: " + erQueue.poll()); // poll() is dequeue()
        // Output: Treating Patient Level: 10
        
        System.out.println("Treating Patient Level: " + erQueue.poll());
        // Output: Treating Patient Level: 5
    }
}

# Python Example: Utilizing the heapq module
import heapq

# Python's heapq only supports Min-Heap (smallest number pops first)
# A common trick is to insert negative numbers to simulate a Max-Heap!
queue = []

# Enqueue (Value, Data)
heapq.heappush(queue, (2, "Update Windows"))
heapq.heappush(queue, (1, "Critical Security Patch")) 
heapq.heappush(queue, (5, "Empty Recycle Bin"))

# Dequeue
priority, task = heapq.heappop(queue)
print(f"Executing: {task}") # Output: Critical Security Patch (Because 1 is the lowest number!)

7. Real-World Applications #

1. 1. Dijkstra's Shortest Path Algorithm: GPS navigation uses a Priority Queue to constantly prioritize exploring the shortest, fastest highway routes over long, slow country roads.

1. 2. Operating System Scheduling: The OS kernel assigns CPU time to hundreds of apps. A user moving their mouse gets Priority Level 1 (instant reaction). A background virus scan gets Priority Level 50 (processed only when the CPU is bored).

1. 3. Bandwidth Management: Internet routers prioritize VoIP video calls (which stutter if delayed) over large email file downloads (where a 2-second delay is invisible).

8. Common Mistakes #

• Assuming it is perfectly sorted: A Priority Queue built on a Heap does *not* perfectly sort all data in memory! It only guarantees that the absolute *maximum* (or minimum) value is sitting at the very top. If you try to print a Priority Queue array directly, the interior numbers will look completely jumbled.

9. Best Practices #

• Custom Objects require Comparators: If you place a custom Student object into a Java PriorityQueue, the queue will crash because it has no idea how to rank a "Student." You must explicitly pass a Comparator interface that tells the Queue to rank them by student.gpa or student.age.

10. Exercises #

1. 1. If you insert (Priority 5, "A"), (Priority 1, "B"), (Priority 9, "C") into a Max-Priority Queue (higher number = higher priority), what is the exact output order of 3 dequeue operations?

1. 2. Explain why an OS Kernel uses a Priority Queue instead of a FIFO Queue for task management.

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Coding:* "Given N massive files containing unsorted integers, write an algorithm to merge all N files into a single perfectly sorted file using the least amount of RAM." *(Answer: Use a Min-Priority Queue! Push the first number from each file into the queue. Pop the smallest, write it, and push the next number from that specific file. It merges infinitely large files using only O(N) RAM!).*

Common Pitfalls:

• In whiteboard interviews, manually writing an O(n) loop to insert data into a sorted array when asked for a Priority Queue. You must explicitly state to the interviewer: "I will utilize the language's native Heap-based Priority Queue library to achieve O(log n) insertions."

13. FAQs #

14. Summary #

15. Next Chapter Recommendation #