Chapter 3.10.4: Priority Queues

Welcome to the advanced data structures section! You’ve already mastered Stacks (LIFO) and standard Queues (FIFO). Now, we are looking at a structure that doesn’t care about when you arrived—it only cares about how important you are! This is the Priority Queue.

Understanding Priority Queues is crucial because they form the basis for many complex algorithms used in routing, scheduling, and efficient data handling.

1. What is a Priority Queue?

A Priority Queue is an advanced data structure where the order in which elements are removed depends solely on the element’s priority, not its arrival time.

It acts like a queue, but it completely breaks the First-In, First-Out (FIFO) rule.

Analogy: The Hospital Emergency Room (Triage)

Imagine you arrive at the emergency room. You don't get treated just because you arrived first. Instead, a triage nurse assesses your situation and assigns a priority level:

  • Patient 1 (Arrived 9:00 AM) - Broken toe (Low Priority: 3)
  • Patient 2 (Arrived 9:15 AM) - Chest pain (High Priority: 1)
  • Patient 3 (Arrived 9:30 AM) - Minor burn (Medium Priority: 2)

Even though Patient 1 arrived first, Patient 2 (Priority 1) will be seen before everyone else. The Priority Queue ensures the most urgent case is always handled next.

Key Rule: The element with the highest priority is always the one that is retrieved (dequeued) next.

Note: If two items have the same priority, they typically follow the standard FIFO rule relative to each other.

Quick Review:

Standard Queue: First In, First Out (FIFO).

Priority Queue: Highest Priority Out First (HPIFO).

2. Priority Queue Operations

Like a standard queue, the core operations are adding an item and removing an item.

2.1. Adding an Item (Enqueue)

When you enqueue an item, you must associate it with a priority value. The position where the item is stored in the underlying structure (like an array) depends on how you implement the queue to maintain the priority order.

Example: Enqueue (Item: "Send Email", Priority: 5)

2.2. Removing an Item (Dequeue)

The dequeue operation removes and returns the item that currently holds the highest priority.

Example: If the item "System Critical Alert" has Priority 10, and no other item has Priority 10, that item is dequeued, regardless of when it was added.

3. Implementation using a One-Dimensional Array

The syllabus requires us to understand how a Priority Queue can be implemented using a one-dimensional array.

Since the array itself doesn't inherently understand "priority," we must create a structure or rule set that imposes the priority logic on the array storage.

Design Decision: How to store the data?

When using an array for a Priority Queue, there are two main ways to handle the data/priority pairing:

Option 1: Unsorted Array (Simpler Enqueue, Slower Dequeue)

Items are simply added to the next available position in the array (like a standard linear queue). This is very fast (O(1) time complexity).

  • Enqueue: Add to the end.
  • Dequeue: To remove the highest priority item, the algorithm must scan through the *entire* array to find the item with the best priority. This is slow (O(n) time complexity, where \(n\) is the number of items).

Option 2: Sorted Array (Slower Enqueue, Faster Dequeue)

Items are inserted into the array such that the array is always kept in order of priority (e.g., highest priority item is always at index 0). This is the more common approach when efficiency in retrieval is key.

  • Enqueue (Adding): When a new item arrives, we must find its correct position based on its priority and shift all lower-priority items down to make space. This can be slow (O(n)).
  • Dequeue (Removing): The item with the highest priority is guaranteed to be at a fixed position (usually the front/start index). Removal is very fast (O(1)).

Don't worry if this seems tricky at first! The core concept is managing the array pointers to ensure we respect priority order.

3.1. Implementation Checks (Empty or Full)

Regardless of whether the array is sorted or unsorted, checking the status of the queue involves tracking the pointers/indices used to manage the array.

We typically use three variables when implementing a queue structure in an array:

  • QUEUE_ARRAY: The one-dimensional array holding the data.
  • Size: The maximum capacity of the array.
  • Count (or pointers like Front/Rear): Tracks the number of items currently in the queue.

Testing if the Priority Queue is Empty

A Priority Queue implemented in an array is empty if the number of items stored is zero.

Implementation Check (using a Count variable):
IF Count == 0 THEN Queue_is_Empty

Testing if the Priority Queue is Full

A Priority Queue implemented in an array is full if the number of items stored equals the maximum size of the array.

Implementation Check (using a Count variable):
IF Count == Size THEN Queue_is_Full

Common Mistake to Avoid

Do not confuse a Priority Queue with sorting algorithms! While insertion into a sorted array (Option 2) looks like sorting, the structure's primary role is managing retrieval, not permanent sorting of a dataset. We only care about which item is *next*.

4. Appropriate Use of Priority Queues (Applications)

Priority Queues are essential whenever resource management or sequential processing must be based on importance rather than chronology.

  • Operating System Scheduling: Managing processes. A critical system process (e.g., handling an interrupt or error) must execute before a background task (e.g., defragmenting a disk), even if the background task was submitted first.
  • Event Simulation: In simulations, events must be handled in the chronological order of their scheduled time, which acts as a priority (earliest time = highest priority).
  • Bandwidth Management: Prioritising network packets. Important data packets (like video conferencing traffic) should be sent before less critical data (like a large file download).
  • Graphing Algorithms: Priority queues are used to implement some critical graphing algorithms.
Did you know?

The shortest path algorithm, Dijkstra’s algorithm, relies heavily on a Priority Queue to efficiently select which node to visit next—it always prioritises the node with the shortest accumulated distance from the start, effectively treating distance as priority!

Key Takeaway

A Priority Queue processes items based on an assigned priority value. While it can be implemented simply using a one-dimensional array, this often requires constant shifting or searching to maintain priority order. It is crucial for systems that require tasks to be handled by importance.