Priority Queue

A normal queue is fair. Whoever comes first gets served first. But sometimes fairness is the wrong rule. Think about an emergency room. A person with a small cut should not go before a person having a heart attack, even if the cut came first. We need a queue that serves by urgency, not by arrival time. That is exactly what a priority queue does.

🏥 A Real-World Picture

Picture the waiting area of a hospital emergency room.

People keep walking in. One has a fever. One broke an arm. One is having chest pain. They did not arrive in any neat order. So the nurse does not call them by who came first. The nurse looks at how serious each case is. Then the nurse calls the most urgent person next.

That is a priority queue in real life. A priority queue is a collection where every item carries a priority. The item with the highest priority always comes out first. The arrival order does not decide who leaves. The priority does.

So the patient with chest pain goes in first. Then the broken arm. The fever waits, because it is the least urgent. When a new critical patient walks in, they jump ahead of everyone who is less urgent. They do not have to stand at the back of the line.

🎯 What a Priority Queue Really Is

Let us pin down the idea in plain words.

A priority queue is like a normal queue with one twist. Instead of “first in, first out”, it does “most important, out first”. Each item has a number we call its priority. When you remove an item, you always get the one with the best priority.

Here is the thing you have to decide up front. What does “best” mean for you?

• In a min-priority queue, the smallest value has the highest priority. The smallest number comes out first.
• In a max-priority queue, the largest value has the highest priority. The largest number comes out first.

Both are normal. A min-priority queue is great when small means urgent, like a task with the nearest deadline. A max-priority queue is great when big means important, like the highest bid in an auction.

🤔 Why Not Just Sort the List Every Time?

That is a fair question. You could keep all items in a list and sort it whenever you need the top one. So why bother with a special structure?

Because sorting again and again is slow. The pain shows up the moment your data keeps changing.

• Every time you add one new item, re-sorting the whole list costs O(n log n). That is a lot of work just to add one thing.
• Most of the time you only care about the single top item, not the full sorted order. Sorting everything to read one value is wasteful.
• Real systems add and remove items all day long. Think of a task scheduler, a network router, or a game engine. The cost of constant re-sorting piles up fast.

A priority queue gives you the top item fast. It also lets you add new items fast, without ever sorting the whole thing. To do that, it uses a clever structure underneath called a heap.

⚙️ How It Works Inside: The Heap

You almost never build a priority queue from scratch. Inside, it is usually a heap. A heap is a special tree-shaped structure where the most important item always sits at the very top, ready to be taken out.

You do not need every detail of heaps right now. Just hold on to the shape of the idea.

• The top of the heap is always the highest-priority item. So reading the top is instant.
• When you add an item, it slides up the tree until it sits in the right spot. This is fast because the tree is short.
• When you remove the top, the heap quickly reshapes itself so the next most important item rises to the top.

Because a heap is a balanced tree, its height stays small. That is why insert and remove each cost only O(log n), not O(n).

Here is the rough shape of a min-heap holding the numbers 3, 5, 8, 10, 14. Notice the smallest value sits at the top.

The number 3 is the smallest, so it sits on top. Remove it, and 5 rises up to become the new top. The structure keeps the best item one step away at all times.

🛠️ Priority Queues in Each Language

Here is the good news. You rarely write the heap yourself. Most languages give you a ready-made priority queue. Let us see the same simple demo in each one.

The demo is the same everywhere. We push a few numbers in any order. Then we pop them out one by one and watch them come out in priority order, smallest first.

#include <stdio.h>

int heap[100];
int size = 0;

// Move a new item up to its correct spot
void push(int value) {
    heap[size] = value;
    int i = size;
    size++;
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
        int tmp = heap[i];
        heap[i] = heap[(i - 1) / 2];
        heap[(i - 1) / 2] = tmp;
        i = (i - 1) / 2;
    }
}

// Remove and return the smallest item (the top)
int pop() {
    int top = heap[0];
    size--;
    heap[0] = heap[size];
    int i = 0;
    while (1) {
        int left = 2 * i + 1, right = 2 * i + 2, small = i;
        if (left < size && heap[left] < heap[small]) small = left;
        if (right < size && heap[right] < heap[small]) small = right;
        if (small == i) break;
        int tmp = heap[i];
        heap[i] = heap[small];
        heap[small] = tmp;
        i = small;
    }
    return top;
}

int main() {
    push(8);
    push(3);
    push(5);
    push(1);
    while (size > 0) {
        printf("%d ", pop());
    }
    printf("\n");
    return 0;
}

1 3 5 8

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // Min-priority queue: smallest comes out first
    priority_queue<int, vector<int>, greater<int>> pq;

    pq.push(8);
    pq.push(3);
    pq.push(5);
    pq.push(1);

    // Pop items one by one in priority order
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

1 3 5 8

import java.util.PriorityQueue;

public class PriorityQueueDemo {
    public static void main(String[] args) {
        // Min-priority queue by default
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.add(8);
        pq.add(3);
        pq.add(5);
        pq.add(1);

        // poll() removes and returns the smallest item
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
        System.out.println();
    }
}

1 3 5 8

import heapq

def priority_queue_demo():
    pq = []  # a plain list, treated as a heap

    # Push numbers in any order
    heapq.heappush(pq, 8)
    heapq.heappush(pq, 3)
    heapq.heappush(pq, 5)
    heapq.heappush(pq, 1)

    # Pop them out smallest first
    result = []
    while pq:
        result.append(heapq.heappop(pq))
    print(result)

priority_queue_demo()

[1, 3, 5, 8]

// Simple array-based priority queue (fine for small data)
function priorityQueueDemo() {
  const pq = [];

  // Push numbers in any order
  pq.push(8);
  pq.push(3);
  pq.push(5);
  pq.push(1);

  // Sort, then pop the smallest each time
  const result = [];
  while (pq.length > 0) {
    pq.sort((a, b) => a - b); // smallest first
    result.push(pq.shift());
  }
  console.log(result.join(" "));
}

priorityQueueDemo();

1 3 5 8

⏱️ How Fast Is It?

Speed is the whole reason we use a heap inside. Here is what each operation costs when the priority queue is built on a heap.

Compare that with the sort-every-time idea, where each insert dragged you back to O(n log n). The heap turns a slow, repeated chore into a quick, cheap step. That gap is why priority queues run inside so many real systems, from Dijkstra’s shortest-path algorithm to operating system schedulers.

⚠️ Common Mistakes to Avoid

A few traps catch people the first time they use a priority queue.

• Forgetting min versus max. C++ priority_queue defaults to max first. Java PriorityQueue and Python heapq default to min first. Always check which one you have before trusting the order.
• Expecting arrival order. A priority queue does not remember who came first. If two items tie on priority, the order between them is not guaranteed. Do not rely on it.
• Trying to peek into the middle. A priority queue only promises fast access to the top item. Searching for some other item inside is slow, around O(n). Use it for “give me the best one”, not for general lookup.
• Using a sorted array for heavy work. Sorting on every insert feels easy but turns slow as data grows. For large or fast-changing data, reach for a real heap.

🧩 What You’ve Learned

✅ A priority queue serves the most important item first, not the oldest, like an emergency room calling the most urgent patient.

✅ You choose the rule: a min-priority queue pops the smallest first, a max-priority queue pops the largest first.

✅ Inside, it is usually a heap, which keeps the best item at the top and stays a short, balanced tree.

✅ That heap gives you O(1) peek and O(log n) insert and remove, far better than re-sorting a list every time.

✅ Each language helps differently: C++ priority_queue, Java PriorityQueue, Python heapq, while C and JavaScript usually need a small heap or array of your own.

🚀 What’s Next?

Now that you know how a priority queue serves the most important item first, look at these next:

• Deque — a flexible queue where you can add and remove from both ends.
• Introduction to Heap — the structure that powers the priority queue, explained from the ground up.