Heap / Priority Queue

Heap गुण

Min-heap में हर parent ≤ उसके children, तो सबसे छोटा तत्व root पर — peek O(1)। Push और pop तत्व को ऊपर/नीचे bubble करके गुण बहाल करते हैं O(log n) में। Array में: i के children 2i+1, 2i+2।

अस्पताल triage

मरीज़ आगमन क्रम में नहीं, गंभीरता से देखे जाते हैं। सबसे ज़रूरी हमेशा अगला, और नया मरीज़ जोड़ने पर सिर्फ़ स्थानीय पुनःक्रम।

Heap से Top-K

आकार-K min-heap रखें; K सबसे बड़े में सबसे छोटा root पर बैठता है और पहले निकाला जाता है।

import heapq
def k_largest(nums, k):
    h = []
    for n in nums:
        heapq.heappush(h, n)
        if len(h) > k:
            heapq.heappop(h)   # drop the smallest
    return sorted(h, reverse=True)

Output:

k_largest([3,1,5,12,2,11], 3) -> [12, 11, 5]

कब उपयोग करें

"K सबसे बड़े/छोटे", "stream का median", "K sorted lists merge", Dijkstra, और कोई भी scheduler जिसे हमेशा वर्तमान सर्वश्रेष्ठ वस्तु चाहिए।