بناء Heap وPush وPop من الصفر

بناء الصنف MinHeap

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if len(self._data) == 1:
            return self._data.pop()
        min_val = self._data[0]
        self._data[0] = self._data.pop()  # move last to root
        self._sift_down(0)
        return min_val

    def peek(self):
        return self._data[0] if self._data else None

    def size(self):
        return len(self._data)

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

print('MinHeap class skeleton defined')

تنفيذ الرفع

class MinHeap:
    def __init__(self):
        self._data = []

    def _parent(self, i): return (i - 1) // 2
    def _left(self, i):   return 2 * i + 1
    def _right(self, i):  return 2 * i + 2

    def _sift_up(self, i):
        while i > 0:
            p = self._parent(i)
            if self._data[p] > self._data[i]:  # parent > child: swap
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else:
                break  # heap property satisfied

    def push(self, val):
        self._data.append(val)
        self._sift_up(len(self._data) - 1)

h = MinHeap()
for v in [5, 3, 8, 1, 4]:
    h.push(v)
print(h._data)  # valid min-heap

تنفيذ الخفض

def _sift_down(data, i):
    n = len(data)
    while True:
        smallest = i
        l = 2 * i + 1
        r = 2 * i + 2
        if l < n and data[l] < data[smallest]:
            smallest = l
        if r < n and data[r] < data[smallest]:
            smallest = r
        if smallest == i:
            break  # already the smallest among i, l, r
        data[i], data[smallest] = data[smallest], data[i]
        i = smallest

# Test: put a large value at root and sift down
heap = [10, 1, 2, 3, 4, 5, 6]
print('Before sift-down:', heap)
_sift_down(heap, 0)
print('After sift-down:', heap)  # 1 should reach top, 10 sink

إكمال MinHeap باستخدام Pop

class MinHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] > self._data[i]:
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()  # last -> root
        i, n = 0, len(self._data)
        while True:
            s, l, r = i, 2*i+1, 2*i+2
            if l < n and self._data[l] < self._data[s]: s = l
            if r < n and self._data[r] < self._data[s]: s = r
            if s == i: break
            self._data[i], self._data[s] = self._data[s], self._data[i]
            i = s
        return result

h = MinHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [1,2,3,4,5,8] sorted

خوارزمية Floyd لبناء الكومة

def heapify(arr):
    n = len(arr)
    # Start from last non-leaf: index n//2 - 1
    # Work backward to root (index 0)
    for i in range(n // 2 - 1, -1, -1):
        # Sift down node at index i
        j = i
        while True:
            s = j
            l, r = 2*j+1, 2*j+2
            if l < n and arr[l] < arr[s]: s = l
            if r < n and arr[r] < arr[s]: s = r
            if s == j: break
            arr[j], arr[s] = arr[s], arr[j]
            j = s
    return arr

arr = [9, 7, 5, 3, 1, 8, 2, 4, 6]
print('Before:', arr)
heapify(arr)
print('After (min-heap):', arr)  # arr[0] should be 1

لماذا تعمل خوارزمية Floyd في O(n)

import time
import random

# Compare: O(n) heapify vs O(n log n) one-by-one
n = 100000
data = list(range(n, 0, -1))  # reverse sorted = worst case for push

# Method 1: Floyd's O(n)
data1 = data[:]
start = time.time()
for i in range(n // 2 - 1, -1, -1):
    j = i
    while True:
        s = j; l, r = 2*j+1, 2*j+2
        if l < n and data1[l] < data1[s]: s = l
        if r < n and data1[r] < data1[s]: s = r
        if s == j: break
        data1[j], data1[s] = data1[s], data1[j]; j = s
print(f'Floyd heapify: {time.time()-start:.4f}s')

# Method 2: One-by-one insertion
import heapq
start = time.time()
heap = []
for x in data: heapq.heappush(heap, x)
print(f'Push one-by-one: {time.time()-start:.4f}s')

دفع عنصر إلى مجموعة موجودة

import heapq

heap = [1, 3, 5, 7, 9]
heapq.heapify(heap)

# heappushpop: push 2, then pop minimum
# More efficient than push + pop separately
result = heapq.heappushpop(heap, 2)
print('heappushpop(2):', result, '| heap:', heap)

# heapreplace: pop minimum, then push new item
# New item does NOT need to be larger (different from heappushpop)
result2 = heapq.heapreplace(heap, 4)
print('heapreplace(4):', result2, '| heap:', heap)

# Use case: maintaining a fixed-size top-k heap
# heappushpop is the standard pattern

تنفيذ MaxHeap من الصفر

class MaxHeap:
    def __init__(self):
        self._data = []

    def push(self, val):
        self._data.append(val)
        i = len(self._data) - 1
        while i > 0:
            p = (i - 1) // 2
            if self._data[p] < self._data[i]:  # FLIP: parent < child = violation
                self._data[p], self._data[i] = self._data[i], self._data[p]
                i = p
            else: break

    def pop(self):
        if not self._data: return None
        if len(self._data) == 1: return self._data.pop()
        result = self._data[0]
        self._data[0] = self._data.pop()
        i, n = 0, len(self._data)
        while True:
            g = i; l, r = 2*i+1, 2*i+2
            if l < n and self._data[l] > self._data[g]: g = l  # FLIP
            if r < n and self._data[r] > self._data[g]: g = r  # FLIP
            if g == i: break
            self._data[i], self._data[g] = self._data[g], self._data[i]; i = g
        return result

h = MaxHeap()
for v in [5, 3, 8, 1, 4, 2]: h.push(v)
print([h.pop() for _ in range(6)])  # [8,5,4,3,2,1]

حذف عنصر عشوائي من الكومة

def delete_at_index(heap, i):
    n = len(heap)
    heap[i] = heap[n - 1]
    heap.pop()
    if i >= len(heap):
        return  # deleted the last element
    # Try sift-up first
    p = (i - 1) // 2
    if i > 0 and heap[i] < heap[p]:
        while i > 0:
            p = (i - 1) // 2
            if heap[p] > heap[i]:
                heap[p], heap[i] = heap[i], heap[p]; i = p
            else: break
    else:  # sift down
        j = i; n2 = len(heap)
        while True:
            s = j; l, r = 2*j+1, 2*j+2
            if l < n2 and heap[l] < heap[s]: s = l
            if r < n2 and heap[r] < heap[s]: s = r
            if s == j: break
            heap[j], heap[s] = heap[s], heap[j]; j = s

heap = [1, 3, 2, 7, 4, 5, 6]
print('Before:', heap)
delete_at_index(heap, 2)  # delete element at index 2 (value=2)
print('After:', heap)  # 2 removed, heap still valid

الكومة في مسألة أكثر العناصر تكراراً

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    # Min-heap of (frequency, num)
    heap = []
    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)  # remove least frequent
    return [num for freq, num in heap]

print(top_k_frequent([1,1,1,2,2,3], 2))  # [1, 2]
print(top_k_frequent([4,4,4,3,3,2,1], 2)) # [4, 3]

تطبيقات الكومات في الجدولة

import heapq

# Simple event-driven simulation using a heap
events = []  # (time, event_description)

def schedule(time, event):
    heapq.heappush(events, (time, event))

def process_next():
    time, event = heapq.heappop(events)
    print(f't={time}: {event}')
    return time, event

# Schedule events out of order:
schedule(10, 'Send email')
schedule(3,  'Open app')
schedule(7,  'Process request')
schedule(1,  'Start server')

# Process in time order:
while events:
    process_next()
# Output: t=1, t=3, t=7, t=10 -- always in time order

اختبار سريع

مراجعة الدرس