Introduction: Getting to the Front of the Line!

Welcome to our study notes on Priority Queues! In your previous lessons, you likely learned about standard Queues (like a line at a grocery store) where the rule is simple: First-In, First-Out (FIFO).

But what happens if someone has an emergency? Or what if a "VIP" arrives? In computer science, we don't always want to process items in the exact order they arrived. Sometimes, some items are more important than others. That is where the Priority Queue comes in! By the end of these notes, you’ll understand how these structures work and why they are essential for making computers run efficiently.

1. What is a Priority Queue?

A Priority Queue is a special type of data structure where every element has a "priority" associated with it. In this queue, an element with high priority is served before an element with low priority.

Prerequisite Check: Remember that a standard Queue (Section 3.2.3 of your syllabus) is FIFO. If you arrive first, you leave first. In a Priority Queue, your position in line depends on your "importance," not just your arrival time.

Real-World Analogy: The Hospital Emergency Room

Imagine you are at a hospital. If you have a small papercut, you might arrive at 10:00 AM. If someone else arrives at 10:15 AM with a broken leg, they will be seen by the doctor before you. Even though you arrived first, their "priority" is higher. This is exactly how a priority queue works!

Key Logic Rules:

1. Elements with higher priority are dequeued (removed) before elements with lower priority.
2. If two elements have the same priority, they are usually served according to their arrival order (FIFO).

Quick Tip: Don't worry if this seems tricky at first! Just remember: Priority = Privilege. The more important you are, the faster you get out of the queue.

Key Takeaway: A priority queue doesn't just care about when you arrived; it cares about who you are (your priority level).

2. How it Works: Operations

Just like a regular queue, we have two main actions, but they work a little differently here:

Enqueue (Adding an Item)

When you add an item to a priority queue, you must provide two things: the data and the priority value.
Example: (Data: "Print Homework", Priority: 2)

Dequeue (Removing an Item)

When the computer asks to remove an item, the priority queue looks through all the items and picks the one with the highest priority. It doesn't necessarily take the one at the very front of the list; it takes the most important one.

Did you know? In some systems, a lower number (like 1) represents the highest priority, while in others, a higher number is more important. Always check the rules of the specific problem you are solving!

Key Takeaway: Enqueue adds an item with a "rank," and Dequeue always grabs the highest-ranked item available.

3. Implementing a Priority Queue

According to section 3.2.1 of your syllabus, you should be familiar with using Arrays and Lists. There are two common ways to build a priority queue using these:

Method A: The Unordered Array

You just add new items to the end of the array (very fast!). However, when you want to Dequeue, the computer has to search through the entire array to find the item with the highest priority. This can be slow if the queue is very long.

Method B: The Ordered Array

Every time you Enqueue a new item, you "insert" it into the correct spot so the array stays sorted by priority. This makes Dequeue incredibly fast because the most important item is always at the front! However, adding items (Enqueue) takes more work because you have to shift other items out of the way.

Common Mistake to Avoid: Students often think a priority queue must always be sorted. Actually, it just needs to behave like one. You can store data however you want, as long as the Dequeue operation always returns the highest priority item.

Key Takeaway: You can choose between making it easy to add items or easy to remove items, depending on what your program needs most.

4. Why do we use them?

Priority queues are used everywhere in Computer Science! Here are a few examples that relate to your syllabus:

  • Operating System Scheduling: (Section 3.6.2) Your computer's Operating System uses a priority queue to decide which programs get to use the Processor. Important tasks (like moving your mouse cursor) have higher priority than background tasks (like downloading an update).
  • Network Traffic: Routers use priority queues to make sure video calls (which need to be fast) are sent before simple emails.
  • Algorithms: Many complex search algorithms (which you may study in A-Level) use priority queues to find the "shortest path" between two points.

Quick Review Box

Standard Queue: First-In, First-Out (FIFO). Like a line for bus tickets.
Priority Queue: Most important first. Like an Emergency Room.
Key Operations: Enqueue (add with priority) and Dequeue (remove highest priority).
Implementation: Can be done with Arrays or Lists (Ordered or Unordered).

Memory Aid: Think of the P in Priority as Pressing. The most Pressing (urgent) task always goes first!

Summary Table

Standard Queue: Processed by Arrival Time.
Priority Queue: Processed by Importance/Rank.
Equal Priority: Usually handled as FIFO.