Priority Queue — Data Structures

What is a Priority Queue?

You already know what a normal queue is — people stand in line, and the one who comes first gets served first (FIFO: First In, First Out).

But what if the line isn’t fair anymore?
What if some people have special priority — like VIPs, ambulances, or emergency messages?

That’s when we need a Priority Queue.

A Priority Queue is a special kind of queue where each element is assigned a priority, and the element with the highest priority is served first — not necessarily the one that arrived first.

---

🎯 Real-Life Example

Imagine you’re in a hospital emergency room.

• A patient with a small cut comes first.
• Then an accident victim arrives later.
• Who gets treated first?

Of course, the accident victim! 🚑
Even though they arrived later, their priority is higher.

That’s exactly how a Priority Queue works.

---

⚙️ Basic Concept

In a priority queue, each item has two parts:

Element	Priority
Data	A value that decides how important it is

• The highest priority item is removed first.
• If two items have the same priority, they follow the FIFO rule.

---

🧱 Diagram of a Priority Queue

Let’s imagine a simple queue with elements and their priorities:

Element	Priority
30	3
10	1
40	2

Now, if we remove (dequeue) from this queue —
we don’t take out the first inserted element (30),
we take out the highest priority one — the one with priority 1 (if smaller number = higher priority).

So, the order of removal will depend on the priority, not on the order of arrival.

---

🧩 Types of Priority Queues

There are mainly two types of priority queues based on how we define “priority”:

1. Ascending Priority Queue

• Elements with lower priority number are served first.
  (e.g., 1 is served before 3)

2. Descending Priority Queue

• Elements with higher priority number are served first.
  (e.g., 5 is served before 2)

It all depends on how the system is designed.

---

🧮 Simple Illustration

Here’s how a Priority Queue might look visually:

+----------------------------+
| Element | Priority         |
+----------------------------+
|   A     |   3              |
|   B     |   1              |
|   C     |   4              |
|   D     |   2              |
+----------------------------+

Now, when we remove (dequeue),
the order will be: B → D → A → C
(based on priority: 1 → 2 → 3 → 4)

---

🔧 Common Operations in a Priority Queue

Just like a normal queue, but with a twist:

1. Insertion (Enqueue)

Add a new element to the queue along with its priority.
The queue is then rearranged so that elements are ordered according to their priority.

Example:
If we insert (E, 1) into a queue containing
(A, 3), (B, 2), (C, 4),
the queue becomes: (E, 1), (B, 2), (A, 3), (C, 4)

---

2. Deletion (Dequeue)

Remove the element with the highest priority (not necessarily the first inserted).

If we remove from the queue above,
(E, 1) will be deleted first because its priority is the highest.

---

3. Peek (Front Element)

This operation shows which element currently has the highest priority —
the one that would be removed next — without actually removing it.

---

🧩 Diagram — Priority Queue Example

Here’s a simple text-based diagram to visualize it:

Before Deletion:
+------------------------------------+
| (Task1, Priority 3) | (Task2, 1) | (Task3, 2) |
+------------------------------------+
Front → Task2 (Highest Priority)

After dequeue, Task2 is removed:

After Deletion:
+--------------------------+
| (Task3, 2) | (Task1, 3) |
+--------------------------+

---

💻 How Priority Queues Are Implemented

There are a few common ways to build a priority queue:

Implementation	Description
Array / List	Elements are stored in an array and sorted by priority after every insertion. Simple, but slow for large data.
Linked List	Similar to array, but insertion and deletion are easier.
Heap (Binary Heap)	The most efficient way! Keeps highest (or lowest) priority element at the top, used in most real-world systems.

---

🧠 Real-Life Uses of Priority Queues

You might be surprised at how often you see them in action:

1. 🖥 Operating Systems: Scheduling processes — the most important task runs first.
2. 📨 Networking: Important data packets (like video calls) are sent before less important ones (like downloads).
3. 🏥 Hospital Management Systems: Emergency cases handled before regular checkups.
4. 🕹 Gaming: Managing events or actions based on urgency.
5. 🧮 Dijkstra’s Algorithm: For finding the shortest path in graphs — uses a priority queue to choose the next closest node.

---

🧠 Example in Pseudocode

Here’s a simple idea of how a priority queue might be handled:

struct Element {
    int data;
    int priority;
};

void enqueue(Element queue[], int data, int priority, int *n) {
    queue[*n].data = data;
    queue[*n].priority = priority;
    (*n)++;
}

int dequeue(Element queue[], int *n) {
    int highestPriority = 0;
    for (int i = 1; i < *n; i++)
        if (queue[i].priority < queue[highestPriority].priority)
            highestPriority = i;

    int value = queue[highestPriority].data;
    for (int i = highestPriority; i < *n - 1; i++)
        queue[i] = queue[i + 1];
    (*n)--;
    return value;
}

Here, lower number = higher priority.

---