Priority Queue — concept (heap-based implementation covered later)

WHAT is a Priority Queue?

WHY the word "abstract"? Because we only promise a contract ("you always get the highest-priority item next"). How we keep things ordered — array, linked list, heap, BST — is a separate choice with different speeds.

WHY do we need it? (The 80/20 core)

Everyday algorithmic uses (the 20% that gives 80% of value):

Dijkstra's shortest path — always expand the closest unvisited node.
Prim's MST — always add the cheapest connecting edge.
Huffman coding — repeatedly merge the two least-frequent symbols.
A* search, event simulation, task schedulers, top-K problems.

HOW does it behave? (Contract, not code)

Imagine a min-priority queue (smaller number = more urgent).

Operation	Meaning	What you get
`insert(A, 5)`	add A, priority 5	—
`insert(B, 2)`	add B, priority 2	—
`insert(C, 8)`	add C, priority 8	—
`peek()`	look at top	B (priority 2)
`extract-min()`	remove top	B
`extract-min()`	remove next	A (priority 5)

Notice C was inserted last but leaves after A and B, because priority — not arrival order — rules.

Figure — Priority Queue — concept (heap-based implementation covered later)

Naive implementations — DERIVE the costs from scratch

Before heaps, let's reason out the simple ways and why they're slow. This shows why heaps are worth learning later.

Option 1: Unsorted array/list

insert: just append at the end. WHY fast? No ordering to maintain → $O(1)$ .
extract-min: you must scan all $n$ elements to find the smallest → $O(n)$ .

Option 2: Sorted array/list (kept sorted by priority)

insert: find the correct slot and shift elements → $O(n)$ .
extract-min: the smallest is already at one end → $O(1)$ .

Formula Cost comparison (derived, not memorised)

Let $n$ = number of elements.

Structure	insert	extract-min
Unsorted list	$O(1)$	$O(n)$
Sorted list	$O(n)$	$O(1)$
Binary heap (later)	$O(\log n)$	$O(\log n)$

WHY the heap wins: naive options make one operation cheap by making the other expensive. If your program does many inserts and many extracts (like Dijkstra), $O(n)$ per operation gives total $O(n^2)$ . A heap balances both at $O(\log n)$ , giving $O(n\log n)$ overall — dramatically faster for large $n$ .

Derivation of the "why balance matters": Suppose you do $n$ inserts and $n$ extracts.

Unsorted: $n\cdot O(1) + n\cdot O(n) = O(n^2)$ .
Sorted: $n\cdot O(n) + n\cdot O(1) = O(n^2)$ .
Heap: $n\cdot O(\log n) + n\cdot O(\log n) = O(n\log n)$ .

For $n=10^6$ : $n^2 = 10^{12}$ vs $n\log_2 n \approx 2\times 10^7$ — about 50,000× faster. That's the payoff.

Worked Examples

Common Mistakes (Steel-man them)

Active Recall

Recall Q: What single property must a priority queue always guarantee?

That peek/extract always returns the element with the highest priority (min or max), regardless of insertion order.

Recall Q: Why is a heap preferred over sorted/unsorted lists?

Naive lists make one operation $O(1)$ but the other $O(n)$ , giving $O(n^2)$ overall. A heap makes both insert and extract $O(\log n)$ → $O(n\log n)$ total.

Recall Q: How do you get max-behaviour from a min-PQ?

Insert negated priorities ( $-p$ ); negate again on extraction.

Recall Feynman: explain to a 12-year-old

Imagine a magic ticket line. Everyone holds a number that says how important they are. No matter when you joined the line, the machine always calls the most important person next. When someone with a scarier number walks in, they don't shove to the front by hand — the machine quietly figures out they should go next. That machine is a priority queue.

Connections

Heap — the standard $O(\log n)$ implementation (covered next).
Binary Tree — a heap is a complete binary tree in disguise.
Queue (FIFO) — contrast: order by arrival, not importance.
Stack (LIFO) — the other basic ordering discipline.
Dijkstra's Algorithm — biggest real-world consumer of a PQ.
Huffman Coding — repeatedly extract two minimums.
Abstract Data Type — PQ is an ADT, heap is a data structure.

What is a priority queue (ADT)?

A collection where each element has a priority; extract always removes the highest-priority (min or max) element, not the earliest inserted.

Core operations of a PQ?

insert(x,p), extract-min/max, peek.

Does a PQ follow FIFO order?

No — removal order is by priority; arrival order only matters for tie-breaking if you enforce it.

extract-min cost in an UNSORTED list?

O(n) — must scan all elements to find the minimum.

insert cost in a SORTED list?

O(n) — must find position and shift elements.

Insert & extract cost in a binary heap?

O(log n) each.

Total cost of n inserts + n extracts with a heap vs naive list?

Heap O(n log n) vs naive O(n^2).

How to simulate a max-PQ using a min-PQ?

Store negated priorities; negate on retrieval.

How to make ties break in FIFO order?

Use a (priority, insertion-sequence) pair as the key.

Why is a PQ called an ADT?

It specifies behaviour (contract), not the underlying implementation.

Two flagship algorithms using a PQ?

Dijkstra's shortest path and Prim's MST (also Huffman coding).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek hospital ka emergency room. Log kisi bhi order mein aayen, doctor sabse pehle usko dekhega jiska case sabse serious hai — heart attack wala finger-cut wale se pehle. Yahi Priority Queue ka core idea hai: har element ke saath ek priority number hota hai, aur jab bhi tum item nikaalte ho, sabse important (min ya max priority) wala nikalta hai — arrival order se koi matlab nahi. Isiliye ye normal FIFO queue se alag hai, jahan sirf "pehle aaya, pehle gaya" chalta hai.

PQ ek ADT hai, matlab wo sirf behaviour (contract) define karta hai — "top hamesha highest priority hoga" — banane ka tareeka alag choice hai. Simple tareeke se banao to do options: unsorted list (insert fast O(1), lekin extract-min slow O(n) kyunki poora scan karna padta hai) ya sorted list (extract fast O(1), lekin insert slow O(n) kyunki shift karna padta hai). Dono mein ek kaam sasta, doosra mehnga — total O(n²).

Yahi problem heap solve karta hai (jo baad mein aayega): insert aur extract dono O(log n), to total O(n log n). Bade n ke liye ye zameen-aasman ka farak hai — n = 10 lakh pe hazaaron guna tez. Isiliye Dijkstra, Prim, Huffman jaise algorithms PQ pe chalte hain.

Do handy tricks yaad rakho: max-PQ chahiye lekin sirf min-PQ hai? Priority ko negative (-p) daalo, nikaalte waqt wapas negate kar do. Aur agar equal priority pe FIFP fairness chahiye, to key ko (priority, sequence-number) bana do — tab purana insert tie jeet jaayega. Bas ye samajh lo: Priority In, Priority Out — queue jo favouritism karti hai!

Priority Queue — concept (heap-based implementation covered later)

WHAT is a Priority Queue?

WHY do we need it? (The 80/20 core)

HOW does it behave? (Contract, not code)

Naive implementations — DERIVE the costs from scratch

Option 1: Unsorted array/list

Option 2: Sorted array/list (kept sorted by priority)

Worked Examples

Common Mistakes (Steel-man them)

Active Recall

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Linear Data Structures

Connections