الترتيب بالكومة

الترتيب بالكومة (heap sort) خوارزمية ترتيب فعّالة قائمة على بنية بيانات الكومة. ويمكننا تنفيذ الترتيب بالكومة باستخدام عمليتي بناء الكومة وإزالة العناصر اللتين قدّمناهما سابقاً.

1. أدخل المصفوفة وابنِ كومة صغرى (min-heap)، وعندها يكون أصغر عنصر في قمة الكومة.
2. نفّذ عمليات إزالة العناصر باستمرار وسجّل العناصر المُزالة بالترتيب للحصول على تسلسل مرتّب تصاعدياً.

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

سير الخوارزمية

لنفترض أن طول المصفوفة $n$. يوضح الشكل أدناه سير الترتيب بالكومة.

1. أدخل المصفوفة وابنِ كومة عظمى (max-heap). وبعد اكتمال البناء، يكون أكبر عنصر في قمة الكومة.
2. بادل عنصر قمة الكومة (العنصر الأول) بعنصر قاعدة الكومة (العنصر الأخير). وبعد اكتمال المبادلة، قلّل طول الكومة بمقدار $1$ وزد عدد العناصر المرتّبة بمقدار $1$.
3. بدءاً من عنصر قمة الكومة، نفّذ عملية إعادة بناء الكومة من الأعلى إلى الأسفل (sift down). وبعد اكتمالها، تُستعاد خصائص الكومة.
4. كرر الخطوتين 2. و3.. وبعد $n - 1$ من الجولات، تكتمل عملية ترتيب المصفوفة.

في الشيفرة أدناه، نستخدم الدالة sift_down() نفسها لإعادة بناء الكومة من الأعلى إلى الأسفل كما في فصل «الكومة». ومن الجدير بالذكر أنه بما أن طول الكومة يتناقص مع استخراج أكبر عنصر، فإننا نحتاج إلى إضافة معامل طول $n$ إلى sift_down() لتحديد الطول الفعلي الحالي للكومة. والشيفرة كما يلي:

/* الترتيب بالكومة */
func heapSort(nums *[]int) {
	// عملية بناء الكومة: أعد بناء جميع العقد عدا الأوراق
	for i := len(*nums)/2 - 1; i >= 0; i-- {
		siftDown(nums, len(*nums), i)
	}
	// استخرج أكبر عنصر من الكومة وكرّر ذلك n-1 مرة
	for i := len(*nums) - 1; i > 0; i-- {
		// حذف العقدة
		(*nums)[0], (*nums)[i] = (*nums)[i], (*nums)[0]
		// ابدأ إعادة بناء الكومة من العقدة الجذرية، من الأعلى إلى الأسفل
		siftDown(nums, i, 0)
	}
}

/* الترتيب بالكومة */
function heapSort(nums: number[]): void {
    // عملية بناء الكومة: أعد بناء جميع العقد عدا الأوراق
    for (let i = Math.floor(nums.length / 2) - 1; i >= 0; i--) {
        siftDown(nums, nums.length, i);
    }
    // استخرج أكبر عنصر من الكومة وكرّر ذلك n-1 مرة
    for (let i = nums.length - 1; i > 0; i--) {
        // حذف العقدة
        [nums[0], nums[i]] = [nums[i], nums[0]];
        // ابدأ إعادة بناء الكومة من العقدة الجذرية، من الأعلى إلى الأسفل
        siftDown(nums, i, 0);
    }
}

خصائص الخوارزمية

• التعقيد الزمني $O(n \log n)$؛ الترتيب بالكومة غير تكيّفي (non-adaptive): يستغرق بناء الكومة زمن $O(n)$. ويستغرق استخراج أكبر عنصر من الكومة زمن $O(\log n)$، ويتكرر ذلك $n - 1$ من الجولات.
• التعقيد المكاني $O(1)$؛ الترتيب بالكومة في المكان (in-place): تستهلك بضع متغيرات من نوع المؤشر مساحة $O(1)$. وتُنفَّذ مبادلة العناصر وإعادة بناء الكومة على المصفوفة الأصلية.
• ترتيب غير مستقر: عند مبادلة عنصر قمة الكومة بعنصر قاعدة الكومة، قد تتغير المواضع النسبية للعناصر المتساوية.