الكومة

الكومة (heap) شجرة ثنائية كاملة تحقق شروطاً محددة، ويمكن تصنيفها أساساً إلى نوعين، كما هو موضح في الشكل أدناه.

• الكومة الصغرى (min heap): قيمة أي عقدة $\leq$ قيم عقدها الفرعية.
• الكومة العظمى (max heap): قيمة أي عقدة $\geq$ قيم عقدها الفرعية.

وباعتبارها حالة خاصة من الشجرة الثنائية الكاملة، تتمتع الأكوام بالخصائص التالية.

• تُملأ عقد الطبقة السفلى من اليسار إلى اليمين، وتكون عقد الطبقات الأخرى ممتلئة بالكامل.
• نسمي العقدة الجذرية للشجرة الثنائية «قمة الكومة»، ونسمي العقدة السفلى في أقصى اليمين «قاع الكومة».
• في الكومة العظمى (الصغرى)، تكون قيمة العنصر الأعلى في الكومة (العقدة الجذرية) هي الأكبر (الأصغر).

عمليات الكومة الشائعة

يجدر بالذكر أن كثيراً من لغات البرمجة توفر طابور الأولوية (priority queue)، وهي بنية بيانات مجردة تُعرّف بأنها طابور تُرتَّب عناصره حسب الأولوية.

وفي الواقع، تُستخدم الأكوام عادةً لتنفيذ طوابير الأولوية، حيث تقابل الكومة العظمى طابور أولوية تُسحب عناصره بترتيب تنازلي. ومن منظور الاستخدام، يمكننا اعتبار «طابور الأولوية» و«الكومة» بنيتي بيانات متكافئتين. لذلك لا يميّز هذا الكتاب بينهما تمييزاً خاصاً، بل يشير إليهما بصفة موحدة باسم «الكومة».

عمليات الكومة الشائعة موضحة في الجدول أدناه، وتتحدد أسماء الدوال وفقاً للغة البرمجة.

جدول   كفاءة عمليات الكومة

في التطبيقات العملية، يمكننا استخدام فئة الكومة (أو فئة طابور الأولوية) التي توفرها لغات البرمجة مباشرةً.

وعلى غرار «الترتيب التصاعدي» و«الترتيب التنازلي» في خوارزميات الترتيب، يمكننا تنفيذ التحويل بين «الكومة الصغرى» و«الكومة العظمى» عبر ضبط flag أو تعديل Comparator. والكود كما يلي:

// في Go، يمكننا إنشاء كومة عظمى من الأعداد الصحيحة عبر تنفيذ heap.Interface
// يتطلب تنفيذ heap.Interface أيضاً تنفيذ sort.Interface
type intHeap []any

// تنفّذ Push دالة الواجهة heap.Interface لإدراج عنصر في الكومة
func (h *intHeap) Push(x any) {
    // تستخدم Push و Pop مستقبِل المؤشر كمعامل
    // لأنهما لا يعدّلان محتوى slice فحسب، بل يعدّلان طوله أيضاً
    *h = append(*h, x.(int))
}

// تنفّذ Pop دالة الواجهة heap.Interface لإخراج العنصر الأعلى في الكومة
func (h *intHeap) Pop() any {
    // يُخزَّن العنصر المطلوب حذفه في النهاية
    last := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return last
}

// Len دالة من واجهة sort.Interface
func (h *intHeap) Len() int {
    return len(*h)
}

// Less دالة من واجهة sort.Interface
func (h *intHeap) Less(i, j int) bool {
    // لتنفيذ كومة صغرى، غيّر هذا إلى علامة أصغر من
    return (*h)[i].(int) > (*h)[j].(int)
}

// Swap دالة من واجهة sort.Interface
func (h *intHeap) Swap(i, j int) {
    (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}

// Top تحصل على العنصر الأعلى في الكومة
func (h *intHeap) Top() any {
    return (*h)[0]
}

/* شيفرة الاختبار */
func TestHeap(t *testing.T) {
    /* تهيئة كومة */
    // هيّئ كومة عظمى
    maxHeap := &intHeap{}
    heap.Init(maxHeap)
    /* إدراج العناصر في الكومة */
    // استدعِ دوال heap.Interface لإضافة العناصر
    heap.Push(maxHeap, 1)
    heap.Push(maxHeap, 3)
    heap.Push(maxHeap, 2)
    heap.Push(maxHeap, 4)
    heap.Push(maxHeap, 5)

    /* الحصول على العنصر الأعلى في الكومة */
    top := maxHeap.Top()
    fmt.Printf("Heap top element is %d\n", top)

    /* حذف العنصر الأعلى في الكومة */
    // استدعِ دوال heap.Interface لإزالة العناصر
    heap.Pop(maxHeap) // 5
    heap.Pop(maxHeap) // 4
    heap.Pop(maxHeap) // 3
    heap.Pop(maxHeap) // 2
    heap.Pop(maxHeap) // 1

    /* الحصول على حجم الكومة */
    size := len(*maxHeap)
    fmt.Printf("Number of heap elements is %d\n", size)

    /* فحص ما إذا كانت الكومة فارغة */
    isEmpty := len(*maxHeap) == 0
    fmt.Printf("Is the heap empty? %t\n", isEmpty)
}

// لا يوفّر TypeScript فئة Heap مدمجة

تنفيذ الكومة

التنفيذ التالي خاص بالكومة العظمى. ولتحويله إلى كومة صغرى، ما عليك سوى عكس كل منطق المقارنة المتعلق بالترتيب (على سبيل المثال، استبدال $\geq$ بـ $\leq$). ونشجّع القرّاء المهتمين على تنفيذ ذلك بأنفسهم.

تخزين الكومة وتمثيلها

كما ذُكر في فصل «الشجرة الثنائية»، تلائم الأشجار الثنائية الكاملة التمثيل بالمصفوفات. ولأن الأكوام نوع من الأشجار الثنائية الكاملة، فإننا سنستخدم المصفوفات لتخزين الأكوام.

عند تمثيل شجرة ثنائية بمصفوفة، تمثل العناصر قيم العقد، وتمثل الفهارس مواضع العقد في الشجرة الثنائية. وتُمثَّل علاقات الأب-الابن عبر صيغ ربط الفهارس.

وكما هو موضح في الشكل أدناه، بمعطى فهرس $i$، يكون فهرس الابن الأيسر $2i + 1$، وفهرس الابن الأيمن $2i + 2$، وفهرس الأب $(i - 1) / 2$ (قسمة أرضية). وعندما يخرج الفهرس عن الحدود، فهذا يشير إلى عقدة فارغة أو إلى أن العقدة غير موجودة.

يمكننا تغليف صيغة ربط الفهارس في دوال لتسهيل استخدامها لاحقاً:

/* الحصول على فهرس العقدة الأب */
func (h *maxHeap) parent(i int) int {
	// قسمة أرضية
	return (i - 1) / 2
}

الوصول إلى العنصر الأعلى في الكومة

العنصر الأعلى في الكومة هو العقدة الجذرية للشجرة الثنائية، وهو أيضاً العنصر الأول في القائمة:

/* الوصول إلى العنصر الأعلى */
func (h *maxHeap) peek() any {
	return h.data[0]
}

إدراج عنصر في الكومة

بمعطى عنصر val، نضيفه أولاً إلى قاع الكومة. وبعد الإدراج، قد تُنتهك خاصية الكومة لأن val قد يكون أكبر من عناصر أخرى في الكومة. لذلك نحتاج إلى استعادة خاصية الكومة على طول المسار من العقدة المُدرجة إلى الجذر. وتسمى هذه العملية تعديل الكومة (heapify).

بدءاً من العقدة المُدرجة، ننفّذ تعديل الكومة من الأسفل إلى الأعلى. وكما هو موضح في الشكل أدناه، نقارن العقدة المُدرجة بالعقدة الأب، وإذا كانت العقدة المُدرجة أكبر نبادلهما. ونواصل هذه العملية من الأسفل إلى الأعلى حتى نتجاوز الجذر أو نصل إلى عقدة لم تعد بحاجة إلى تبادل.

بالمجموع $n$ من العقد، يكون ارتفاع الشجرة $O(\log n)$. ومن ثم، فإن عدد تكرارات الحلقة في عملية تعديل الكومة لا يزيد عن $O(\log n)$، وهو ما يجعل التعقيد الزمني لعملية إدراج العنصر $O(\log n)$. والكود كما يلي:

/* بدءاً من العقدة i، نفّذ تعديل الكومة من الأسفل إلى الأعلى */
func (h *maxHeap) siftUp(i int) {
	for true {
		// احصل على العقدة الأب للعقدة i
		p := h.parent(i)
		// عندما «نتجاوز العقدة الجذرية» أو «لا تحتاج العقدة إلى إصلاح»، أنهِ تعديل الكومة
		if p < 0 || h.data[i].(int) <= h.data[p].(int) {
			break
		}
		// بادل العقدتين
		h.swap(i, p)
		// كرّر تعديل الكومة صعوداً
		i = p
	}
}

حذف العنصر الأعلى في الكومة

العنصر الأعلى في الكومة هو العقدة الجذرية للشجرة الثنائية، وهو العنصر الأول في القائمة. وإذا حذفنا العنصر الأول من القائمة مباشرةً، فستتغير جميع فهارس العقد في الشجرة الثنائية، مما يصعّب الإصلاح اللاحق بتعديل الكومة. ولتقليل تغيّرات فهارس العناصر إلى أدنى حد، نتبع الخطوات التالية.

1. بادل العنصر الأعلى في الكومة بعنصر قاع الكومة (بادل العقدة الجذرية بالعقدة الورقية الأقصى يميناً).
2. بعد التبادل، احذف قاع الكومة من القائمة (لاحظ أننا في الواقع نحذف العنصر الأعلى الأصلي في الكومة لأننا بادلناه).
3. بدءاً من العقدة الجذرية، نفّذ تعديل الكومة من الأعلى إلى الأسفل.

وكما هو موضح في الشكل أدناه، يكون اتجاه «تعديل الكومة من الأعلى إلى الأسفل» معاكساً لاتجاه «تعديل الكومة من الأسفل إلى الأعلى». نقارن قيمة العقدة الجذرية بقيم ابنيها ونبادلها مع الابن الأكبر. ثم نكرّر هذه العملية حتى نتجاوز عقدة ورقية أو نصادف عقدة لا تحتاج إلى تبادل.

وعلى غرار عملية إدراج العنصر، يكون التعقيد الزمني لعملية حذف العنصر الأعلى في الكومة أيضاً $O(\log n)$. والكود كما يلي:

/* بدءاً من العقدة i، نفّذ تعديل الكومة من الأعلى إلى الأسفل */
func (h *maxHeap) siftDown(i int) {
	for true {
		// ابحث عن العقدة ذات القيمة العظمى بين العقد i و l و r، وسمّها max
		l, r, max := h.left(i), h.right(i), i
		if l < h.size() && h.data[l].(int) > h.data[max].(int) {
			max = l
		}
		if r < h.size() && h.data[r].(int) > h.data[max].(int) {
			max = r
		}
		// بادل العقدتين
		if max == i {
			break
		}
		// بادل العقدتين
		h.swap(i, max)
		// كرّر تعديل الكومة نزولاً
		i = max
	}
}

التطبيقات الشائعة للأكوام

• طابور الأولوية: الأكوام عادةً هي بنية البيانات المفضلة لتنفيذ طوابير الأولوية. فالتعقيد الزمني لكل من عمليتي الإدخال والإخراج هو $O(\log n)$، وبناء الكومة له تعقيد زمني $O(n)$، مما يجعل هذه العمليات عالية الكفاءة.
• ترتيب الكومة: بمعطى مجموعة من البيانات، يمكننا بناء كومة منها ثم تنفيذ عمليات حذف العناصر باستمرار للحصول على بيانات مرتبة. غير أننا نستخدم عادةً أسلوباً أكثر أناقة لتنفيذ ترتيب الكومة، كما هو مفصل في فصل «ترتيب الكومة».
• الحصول على أكبر $k$ من العناصر: هذه مسألة خوارزمية كلاسيكية وتطبيق نموذجي أيضاً، مثل اختيار الأخبار العشرة الأكثر رواجاً في «بحث ويبو الساخن» أو المنتجات العشرة الأكثر مبيعاً.