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

3.2.9 · Coding › Linear Data Structures

WHAT is a Priority Queue?

"Abstract" word kyun? Kyunki hum sirf ek contract promise karte hain ("aapko hamesha next highest-priority item milega"). Hum cheezein kaise ordered rakhte hain — array, linked list, heap, BST — yeh alag choice hai alag speeds ke saath.

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

Rozana ke algorithmic uses (woh 20% jo 80% value deta hai):

Dijkstra's shortest path — hamesha closest unvisited node expand karo.
Prim's MST — hamesha sabse sasti connecting edge add karo.
Huffman coding — baar baar do sabse kam-frequent symbols merge karo.
A* search, event simulation, task schedulers, top-K problems.

HOW does it behave? (Contract, not code)

Imagine karo ek min-priority queue (chhota number = zyada urgent).

Operation	Matlab	Kya milta hai
`insert(A, 5)`	A add karo, priority 5	—
`insert(B, 2)`	B add karo, priority 2	—
`insert(C, 8)`	C add karo, priority 8	—
`peek()`	top dekho	B (priority 2)
`extract-min()`	top remove karo	B
`extract-min()`	next remove karo	A (priority 5)

Notice karo C sabse baad insert hua lekin baad mein A aur B ke nikalta hai, kyunki priority — arrival order nahi — rule karta hai.

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

Naive implementations — DERIVE the costs from scratch

Heaps se pehle, simple tarike sochte hain aur kyun woh slow hain. Isse pata chalta hai kyun heaps baad mein seekhne layak hain.

Option 1: Unsorted array/list

insert: bas end pe append karo. WHY fast? Koi ordering maintain nahi karni → $O (1)$ .
extract-min: smallest dhundne ke liye saare $n$ elements scan karne padte hain → $O (n)$ .

Option 2: Sorted array/list (priority ke hisaab se sorted rakha)

insert: sahi slot dhundo aur elements shift karo → $O (n)$ .
extract-min: sabse chhota pehle hi ek end par hai → $O (1)$ .

Formula Cost comparison (derived, memorised nahi)

$n$ = elements ki sankhya.

Structure	insert	extract-min
Unsorted list	$O (1)$	$O (n)$
Sorted list	$O (n)$	$O (1)$
Binary heap (baad mein)	$O (lo g n)$	$O (lo g n)$

WHY heap jeeetta hai: naive options ek operation ko cheap banate hain doosre ko expensive banake. Agar program bahut saare inserts aur bahut saare extracts karta hai (jaise Dijkstra), toh $O (n)$ per operation se total $O (n^{2})$ hoga. Heap dono ko $O (lo g n)$ par balance karta hai, overall $O (n lo g n)$ deta hai — bade $n$ ke liye dramatically faster.

"Why balance matters" ki derivation: Maano tum $n$ inserts aur $n$ extracts karte ho.

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 (lo g n) + n \cdot O (lo g n) = O (n lo g n)$ .

$n = 1 0^{6}$ ke liye: $n^{2} = 1 0^{12}$ vs $n lo g_{2} n \approx 2 \times 1 0^{7}$ — lagbhag 50,000× faster. Yahi fayda hai.

Worked Examples

Common Mistakes (Steel-man them)

Active Recall

Recall Q: Woh ek property kya hai jo priority queue hamesha guarantee karta hai?

Ki peek/extract hamesha highest priority (min ya max) wala element return karta hai, insertion order ki parwah kiye bina.

Recall Q: Heap ko sorted/unsorted lists se kyun prefer karte hain?

Naive lists ek operation ko $O (1)$ banate hain lekin doosre ko $O (n)$ , overall $O (n^{2})$ deta hai. Heap dono insert aur extract ko $O (lo g n)$ banata hai → total $O (n lo g n)$ .

Recall Q: Min-PQ se max-behaviour kaise loge?

Negated priorities ( $- p$ ) insert karo; extraction par phir negate karo.

Recall Feynman: 12-saal ke bacche ko explain karo

Socho ek jaadu ki ticket line. Sabke haath mein ek number hai jo batata hai woh kitne important hain. Chahe tum kab bhi line mein aaye ho, machine hamesha sabse important insaan ko next bulaati hai. Jab koi zyada scary number wala andar aata hai, woh haath se aage nahi dhakelta — machine chupke se figure out kar leti hai ki unhe aage jaana chahiye. Woh machine hai priority queue.

Connections

Heap — standard $O (lo g n)$ implementation (aage cover hoga).
Binary Tree — heap ek complete binary tree chhupe roop mein hai.
Queue (FIFO) — contrast: arrival ke order se, importance se nahi.
Stack (LIFO) — doosra basic ordering discipline.
Dijkstra's Algorithm — PQ ka sabse bada real-world consumer.
Huffman Coding — baar baar do minimums extract karo.
Abstract Data Type — PQ ek ADT hai, heap ek data structure hai.

Priority queue (ADT) kya hai?

Ek collection jahan har element ki ek priority hoti hai; extract hamesha highest-priority (min ya max) element ko remove karta hai, pehle inserted ko nahi.

PQ ke core operations kya hain?

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

Kya PQ FIFO order follow karta hai?

Nahi — removal order priority se hota hai; arrival order sirf tab matter karta hai agar tum tie-breaking enforce karo.

UNSORTED list mein extract-min ki cost?

O(n) — minimum dhundne ke liye saare elements scan karne padte hain.

SORTED list mein insert ki cost?

O(n) — position dhundna padta hai aur elements shift karne padte hain.

Binary heap mein Insert & extract ki cost?

O(log n) dono.

Heap vs naive list ke saath n inserts + n extracts ki total cost?

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

Min-PQ use karke max-PQ kaise simulate karein?

Negated priorities store karo; retrieval par negate karo.

Ties ko FIFO order mein kaise break karein?

Key ke roop mein (priority, insertion-sequence) pair use karo.

PQ ko ADT kyun kehte hain?

Ye behaviour (contract) specify karta hai, underlying implementation nahi.

PQ use karne wale do flagship algorithms?

Dijkstra's shortest path aur Prim's MST (Huffman coding bhi).