Heaps और Priority Queues
Heap क्या है?
Heap एक complete binary tree है जहाँ हर parent heap property satisfy करता है - या तो हमेशा छोटा (min-heap) या हमेशा बड़ा (max-heap) अपने children से। "Complete" का मतलब हर level भरा है, सिवाय शायद last level के जो left से right भरता है।
1 Min-heap
/ \
3 5
/ \
7 4
Complete होने की वजह से इसे flat array में store करते हैं - pointers की ज़रूरत नहीं। Index i के लिए: left child = 2i + 1, right child = 2i + 2, parent = (i - 1) // 2।
Min-Heap vs Max-Heap
| Property | Min-Heap | Max-Heap | |----------|----------|----------| | Root | सबसे छोटा element | सबसे बड़ा element | | Parent ≤ Children? | ✅ हाँ | ❌ नहीं (≥) | | Extract देता है | Minimum | Maximum |
Python का heapq default में min-heap है। Max-heap के लिए insert पर values negate करो और extract पर वापस negate करो।
Insert और Extract - Step by Step
Insert - end पर push करो, फिर bubble up (parent से swap करो जब तक छोटा हो):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
Extract min - root को last element से swap करो, last pop करो, फिर sift down (smaller child से swap):
smallest = heapq.heappop(h) # returns 1
दोनों operations O(log n) में चलते हैं क्योंकि tree की height log n है।
Heapify - O(n) में Heap बनाओ
heapq.heapify(arr) एक list को O(n) में heap बना देता है, O(n log n) नहीं। यह bottom-up काम करता है, हर non-leaf node को sift down करता है।
Discussion
Sign in to join the discussion