الأكوام والهياكل المتقدمة

الأكوام و Trie و Union-Find تظهر بشكل أقل من المصفوفات أو الأشجار لكنها حاسمة لفئات مسائل محددة. معرفة متى تستخدمها يمنحك ميزة كبيرة.

الأكوام (Heaps / قوائم الأولوية)

الكومة هي شجرة متخصصة تحافظ على العنصر الأصغر (min-heap) أو الأكبر (max-heap) في الجذر. وحدة heapq في Python توفر min-heap.

متى تستخدم الكومة:

• إيجاد أكبر/أصغر K عنصر
• دمج K قائمة مرتبة
• إيجاد الوسيط من تدفق بيانات
• جدولة المهام حسب الأولوية

import heapq

# أكثر K عنصر تكرارًا
def top_k_frequent(nums, k):
    freq = {}
    for num in nums:
        freq[num] = freq.get(num, 0) + 1
    # استخدام min-heap بحجم k
    return heapq.nlargest(k, freq.keys(), key=freq.get)

# دمج K قائمة مرتبة
def merge_k_lists(lists):
    heap = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0].val, i, lst[0]))

    dummy = ListNode(0)
    current = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))

    return dummy.next

العملية	التعقيد الزمني
الإدراج	O(log n)
استخراج الأصغر/الأكبر	O(log n)
الاطلاع على الأصغر/الأكبر	O(1)
بناء الكومة	O(n)

Trie (شجرة البادئات)

Trie هي بنية شبيهة بالشجرة لتخزين السلاسل النصية، مُحسّنة لعمليات البادئات.

متى تستخدم Trie:

• الإكمال التلقائي
• البحث عن الكلمات في لوحة
• التدقيق الإملائي
• توجيه IP (أطول بادئة مطابقة)

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

Union-Find (المجموعات المنفصلة)

Union-Find يتتبع المكونات المتصلة بكفاءة. يستخدم تحسينين: ضغط المسار والاتحاد حسب الرتبة.

متى تستخدم Union-Find:

• المكونات المتصلة في رسم بياني
• كشف الدورات في رسوم بيانية غير موجّهة
• خوارزمية Kruskal لأصغر شجرة ممتدة
• عدد الجزر (بديل لـ DFS)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # ضغط المسار
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False  # متصلان بالفعل
        # الاتحاد حسب الرتبة
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True

دليل القرار السريع

إشارة المسألة	هيكل البيانات	مثال
"أكبر K" أو "أصغر K"	الكومة	أكثر K عنصر تكرارًا
"بادئة" أو "إكمال تلقائي"	Trie	تطبيق الإكمال التلقائي
"متصل" أو "مجموعات"	Union-Find	عدد المقاطعات
"الوسيط" أو "تدفق"	كومتان	إيجاد الوسيط من تدفق بيانات
"قاموس كلمات" أو "لوحة"	Trie + DFS	البحث عن الكلمات II

نصيحة للمقابلات: إذا استطعت تحديد هيكل البيانات الصحيح في أول دقيقتين من المسألة، فأنت بالفعل في منتصف الطريق نحو الحل.

---

ممتاز! مع إتقان هياكل البيانات، لننتقل إلى أنماط الخوارزميات التي تربط كل شيء معًا. :::