Heap ও Priority Queue — array-তে বসানো tree

class MinHeap:
    """0-indexed: parent=(i-1)//2, children=2i+1, 2i+2"""

    def __init__(self, items=None):
        self.a = list(items) if items else []
        for i in range(len(self.a) // 2 - 1, -1, -1):   # last parent → root
            self._sift_down(i)

    def __len__(self):
        return len(self.a)

    def push(self, x):
        self.a.append(x)
        self._sift_up(len(self.a) - 1)

    def pop(self):
        top, last = self.a[0], self.a.pop()
        if self.a:
            self.a[0] = last          # গঠন অক্ষত রাখার চাল
            self._sift_down(0)
        return top

    def peek(self):
        return self.a[0]

    def decrease_key(self, i, new_val):
        assert new_val \<= self.a[i], 'increase-এ sift_down লাগত'
        self.a[i] = new_val
        self._sift_up(i)

    def _sift_up(self, i):
        a = self.a
        while i > 0:
            p = (i - 1) // 2
            if a[i] \< a[p]:
                a[i], a[p] = a[p], a[i]; i = p
            else:
                break

    def _sift_down(self, i):
        a, n = self.a, len(self.a)
        while True:
            l, r, m = 2*i + 1, 2*i + 2, i
            if l \< n and a[l] \< a[m]: m = l
            if r \< n and a[r] \< a[m]: m = r
            if m == i:
                return
            a[i], a[m] = a[m], a[i]
            i = m


def k_way_merge(lists):
    """k sorted list → এক sorted list, O(N log k)"""
    h = MinHeap()
    for li, lst in enumerate(lists):
        if lst:
            h.push((lst[0], li, 0))       # (মান, কোন list, কোন index)
    out = []
    while len(h):
        v, li, j = h.pop()
        out.append(v)
        nxt = j + 1
        if nxt \< len(lists[li]):
            h.push((lists[li][nxt], li, nxt))
    return out


if __name__ == '__main__':
    import random
    random.seed(1)

    data = [random.randint(0, 99) for _ in range(15)]
    h = MinHeap(data)
    got = [h.pop() for _ in range(len(h))]
    assert got == sorted(data)
    print('pop order:', got[:6], '...')

    tasks = [(9,'backup'), (7,'report'), (5,'email'), (3,'deploy'), (1,'monitor')]
    q = MinHeap(tasks)
    q.decrease_key(tasks.index((7, 'report')), (0, 'report'))
    order = [q.pop() for _ in range(len(q))]
    assert order[0] == (0, 'report')
    print('after decrease:', order[:3])

    lists = [[1,4,9,16],[2,6,11],[3,8],[0,5,12,20],[7,10]]
    merged = k_way_merge(lists)
    print('merged:', merged)
    assert merged == sorted(sum(lists, []))
    print('সব assert পাস')

প্রত্যাশিত output:

pop order: [8, 12, 15, 17, 26, 32] ...
after decrease: [(0, 'report'), (1, 'monitor'), (5, 'email')]
merged: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 16, 20]
সব assert পাস

merge-হিসাব: heap-এ সবসময় ≤ k=5 entry; প্রতি output element = pop+push = O(log k); মোট O(N log k) — naive concat+sort O(N log N), pairwise O(N·k)-এর বিপরীতে। k ছোট, N বিশাল — external merge sort এখানেই দাঁড়িয়ে।

নিজে বাড়ান: (১) delete(i) = decrease_key(i, −∞)+pop; (২) MaxHeap — comparison উল্টানো বনাম value-negate, pros লিখুন; (৩) indexed version — pos dict swap-এ sync করে decrease_key(item, val) interface (Dijkstra- ready); (৪) নিজের heap vs heapq benchmark — constant-factor gap টের পান, asymptotic একই।