تكرار السؤال: …
الإجابة المختصرة
الكوم الثنائي هو شجرة ثنائية شبه مكتملة تحقق خاصية الكوم (العنصر الأب أصغر من أبنائه في Min-Heap أو أكبر في Max-Heap)، ويُمثل بكفاءة في مصفوفة حيث أبناء العنصر عند المؤشر i يقعان عند 2i+1 و 2i+2.
الشرح
لأن الشجرة مكتملة دائماً، لا نحتاج لتخزين مؤشرات pointers في الذاكرة؛ فالأب عند index يمتلك ابنه الأيسر عند 2*i + 1 والأيمن عند 2*i + 2، والأب عند floor((i-1)/2). تتيح عملية Heapify تحويل مصفوفة عشوائية إلى Heap في زمن خطي O(N) بدلاً من O(N log N) عبر بناء المستويات من الأسفل للأعلى، بينما يستغرق استخراج القمة O(log N).
مثال بالكود
class MinHeap:
def __init__(self):
self.a = []
def push(self, x):
a = self.a
a.append(x)
i = len(a) - 1
while i > 0 and a[(i - 1) // 2] > a[i]: # sift up: parent = (i - 1) // 2
a[(i - 1) // 2], a[i] = a[i], a[(i - 1) // 2]
i = (i - 1) // 2
def pop(self):
a = self.a
a[0], a[-1] = a[-1], a[0]
top = a.pop()
i = 0
while True: # sift down (heapify): children = 2i+1, 2i+2
left, right, smallest = 2 * i + 1, 2 * i + 2, i
if left < len(a) and a[left] < a[smallest]:
smallest = left
if right < len(a) and a[right] < a[smallest]:
smallest = right
if smallest == i:
return top
a[smallest], a[i] = a[i], a[smallest]
i = smallestأخطاء شائعة
- الخلط بين شجرة البحث الثنائية (BST) والكوم الثنائي (Binary Heap)؛ الـ Heap لا يرتب الأبناء الأيسر والأيمن بالنسبة لبعضهما بل بالنسبة للأب فقط.