Data Structures
पाठ · #7 / 11

हीप और प्राथमिकता क़तारें (Heaps & Priority Queues)

ऐरे-आधारित, log-समय में न्यूनतम — प्राथमिकता क़तारों का इंजन

Min-heap · array view ↔ tree view

array 
init

खुद आज़माएँ: insert कीजिए और देखिए कैसे bubble-up की अदला-बदली जोड़े चमकाती है। फिर extractMin — sift-down invariant को बहाल कर देता है। एक ही ऐरे, उसे देखने के दो तरीक़े: कोशिकाओं की क़तार और एक पूर्ण बाइनरी पेड़।

यह क्यों मायने रखता है

हीप वही ऐरे-आधारित पेड़ है जो बाइनरी पेड़ वाले पाठ में था — पर एक अतिरिक्त नियम के साथ जो उसे एक स्थिर-समय वाला min/max इंजन बना देता है। जब आपको अधिकतम (या न्यूनतम) तत्व जल्दी और बार-बार चाहिए, तो हीप ही जवाब है। ये प्राथमिकता क़तारों, heap sort, और Dijkstra के सबसे छोटे पथ जैसे एल्गोरिथ्म को शक्ति देते हैं (जो आपने ग्राफ़ वाले पाठ के shortest-path मोड में देखा)।

हीप अपरिवर्तनी (invariant)

दो invariant, दोनों का टिकना ज़रूरी है:

Heap invariants
आकार (Shape): बाइनरी पेड़ पूर्ण (complete) है — हर स्तर भरा हुआ है सिवाय शायद आख़िरी के, जो बाएँ-से-दाएँ भरता है। इससे हम पेड़ को बिना किसी छेद के, एक ऐरे में लगातार रख सकते हैं।
क्रम (min-heap): हर नोड n के लिए, हर बच्चे के लिए n.key ≤ key(child)। (max-heap के लिए ≥ पर पलट दीजिए।) इसलिए root न्यूनतम (या अधिकतम) रखता है।
"बनाए रखना" का मतलब
Insert पत्ती पर क्रम को कुछ देर के लिए तोड़ता है, फिर bubble-up उसे बहाल करता है। Extract दोनों को कुछ देर के लिए तोड़ता है (आख़िरी पत्ती root पर चली जाती है), फिर sift-down आकार को पूर्ण रखते हुए क्रम बहाल करता है।

मूल विचार

एक टूर्नामेंट ब्रैकेट की कल्पना कीजिए जहाँ विजेता हमेशा ऊपर चढ़ता जाता है। हर मैच के बाद बेहतर टीम ऊपर बढ़ती है।

हीप कुछ ऐसा ही है। एक max-heap में हर माता-पिता अपने बच्चों से बड़ा होता है। root हमेशा अधिकतम होता है।

चतुर तरकीब: इसे एक ऐरे में रखो! इंडेक्स i पर मौजूद नोड के लिए:

Insert: अंत में जोड़ो, फिर "bubble up" करो — जब तक बड़ा हो, माता-पिता से अदला-बदली करते रहो। Extract max: root हटाओ, आख़िरी तत्व को root पर रखो, फिर "sink down" करो — जब तक छोटा हो, बड़े बच्चे से अदला-बदली करते रहो।

दोनों ऑपरेशन O(log n) हैं — बस पेड़ की ऊँचाई जितने।

मुख्य बातें

और गहराई में

Min-heap बनाम max-heap

एक min-heap सबसे छोटे तत्व को root पर रखती है; max-heap सबसे बड़े को। तंत्र एक जैसा है — सिर्फ़ तुलना की दिशा पलटती है। कुछ भाषाएँ एक तरफ़ डिफ़ॉल्ट होती हैं (C++ std::priority_queue max है; Python heapq min है) और पलटने के लिए आप मानों को ऋणात्मक कर देते हैं — heapq.heappush(q, -value)। हमेशा जाँच लीजिए।

O(n) heapify का प्रमाण

आपको लगेगा कि n अव्यवस्थित तत्वों से हीप बनाने में O(n log n) लगेगा — हर तत्व पर एक O(log n) insert। पर एक बेहतर तरीक़ा है: ऐरे को कॉपी कीजिए, फिर बीच के इंडेक्स से root की ओर sift down कीजिए। कुल लागत O(n) है, न कि O(n log n)।

प्रमाण एक ख़ूबसूरत गुणोत्तर श्रेणी है। n नोडों के एक पूर्ण बाइनरी पेड़ में लगभग n/2 पत्तियाँ होती हैं (गहराई 0 — कोई sift नहीं चाहिए), गहराई 1 पर n/4 (हर पर अधिक से अधिक 1 अदला-बदली), गहराई 2 पर n/8 (अधिक से अधिक 2 अदला-बदली), …, गहराई log n पर 1 root (अधिक से अधिक log n अदला-बदली)। कुल काम:

work ≤ Σ (n / 2^(d+1)) · d   for d = 0..log n
     = (n/2) · Σ d / 2^d
     ≤ (n/2) · 2     since Σ d/2^d converges to 2
     = O(n)

ज़्यादातर नोड तले के पास होते हैं और शून्य या एक स्तर sift होते हैं। सिर्फ़ ऊपर के पास का एक नगण्य अंश पूरा log n काम करता है। यह amortized विश्लेषण का एक और रंग है — worst case कुछ ही नोडों पर सिमटा है, और वे इतने कम हैं कि हावी नहीं हो पाते।

हीप बनाम BST — किसे कब चुनें

दोनों आपको O(log n) ऑपरेशन देते हैं। दो व्यावहारिक अंतर तय करते हैं कि किसे इस्तेमाल करें:

| उपयोग | हीप | BST | |---|---|---| | बार-बार min/max निकालना | ✓ O(1) peek, O(log n) pop | min/max के लिए भी O(log n) | | रेंज क्वेरी (50 से बड़े सब ढूँढो) | ✗ कोई क्रम नहीं | ✓ O(log n + k) | | In-order traversal | ✗ | ✓ | | मेमोरी का बोझ | ऐरे — कोई पॉइंटर नहीं | प्रति नोड 2 पॉइंटर + मान | | स्थिरांक (constant factor) | छोटा (ऐरे, कैश-अनुकूल) | बड़ा (पॉइंटर का पीछा करना) | | n तत्वों से बनाना | O(n) heapify | O(n log n) बार-बार insert |

हीप चुनिए जब आपको सिर्फ़ min/max चाहिए और कभी क्रम या रेंज क्वेरी नहीं। BST चुनिए (आम तौर पर संतुलित) जब आपको क्रमबद्ध iteration चाहिए या "[a, b] की सारी key ढूँढो"। ग्राफ़ वाले पाठ का Dijkstra मोड एक हीप इस्तेमाल करता है क्योंकि उसे हमेशा सबसे-सस्ता-अगला frontier नोड चाहिए, न कि सारे frontier नोडों का क्रम।

Heap sort यही इस्तेमाल करता है: O(n) में heapify, फिर n बार extract max — कुल मिलाकर O(n log n) — पर merge sort से ख़राब कैश व्यवहार के साथ, इसलिए मिलते-जुलते asymptote के बावजूद यह शायद ही व्यावहारिक विजेता होता है।

गणितीय ब्यौरा

Time Complexity
Insert: O(log n)
Extract max/min: O(log n)
Peek: O(1)
Heapify (build): O(n)
Array Index Formulas
left(i) = 2i + 1
right(i) = 2i + 2
parent(i) = lfloor(i-1)/2rfloor

क्रियान्वयन (Implementation)

हीप ऑपरेशन

use std::collections::BinaryHeap;

let mut heap = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);  // Heap: max at top

let max = heap.pop();  // Returns Some(4)
let peek = heap.peek(); // Returns Some(&3)

कब इस्तेमाल करें

अभ्यास

तीन सवाल जो दिखाते हैं कि "मुझे सबसे अच्छी/बुरी k चीज़ें दो" के लिए हीप आपका डिफ़ॉल्ट औज़ार क्यों है:

→ सभी अभ्यास सवाल देखें