Heaps మరియు Priority Queues
Heap అంటే ఏమిటి?
Heap అనేది ప్రతి parent heap property ని సంతృప్తిపరిచే complete binary tree - ఎల్లప్పుడూ children కంటే చిన్నది (min-heap) లేదా పెద్దది (max-heap). "Complete" అంటే చివరి level తప్ప ప్రతి level నిండి ఉంటుంది, చివరిది ఎడమ నుండి కుడికి నిండుతుంది.
1 Min-heap
/ \
3 5
/ \
7 4
ఇది complete కాబట్టి, flat array లో నిల్వ చేస్తాం - pointers అవసరం లేదు. Index i కోసం: left child = 2i + 1, right child = 2i + 2, parent = (i - 1) // 2.
Min-Heap vs Max-Heap
| లక్షణం | Min-Heap | Max-Heap | |----------|----------|----------| | Root | అతి చిన్న element | అతి పెద్ద element | | Parent ≤ Children? | ✅ అవును | ❌ కాదు (≥) | | Extract ఇస్తుంది | Minimum | Maximum |
Python heapq డిఫాల్ట్గా min-heap. Max-heap కోసం, insert చేసేటప్పుడు విలువలను negate చేసి, extract చేసేటప్పుడు మళ్ళీ negate చేయండి.
Insert మరియు Extract - అడుగు అడుగునా
Insert - చివరికి push చేసి, bubble up చేయండి (చిన్నదైనంత వరకు parent తో swap):
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h [1, 2, 5, 7, 3] అవుతుంది
Extract min - root ను చివరి element తో swap చేసి, చివరిది తొలగించి, sift down చేయండి (చిన్న child తో swap):
smallest = heapq.heappop(h) # 1 రిటర్న్ చేస్తుంది
రెండు operations O(log n) లో నడుస్తాయి ఎందుకంటే tree ఎత్తు log n.
Heapify - O(n) లో Heap నిర్మించడం
heapq.heapify(arr) ను call చేయడం list ను O(n) లో heap గా మారుస్తుంది, O(n log n) కాదు. ఇది bottom-up పనిచేస్తుంది, ప్రతి non-leaf node ను కిందకు sift చేస్తుంది. CS లో అత్యంత ఆశ్చర్యకరమైన complexity ఫలితాలలో ఇది ఒకటి.
Discussion
Sign in to join the discussion