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

تستند خوارزمية الترتيب بالكومة Heap Sort على الكومة الثنائية Binary Heap، وهي مشابهة لخوارزمية الترتيب بالتحديد Selection Sort إذ نختار في البداية العنصر الأكبر في المصفوفة ونضعه في نهاية المصفوفة، وتعاد العملية على بقية العناصر.

لمّا كانت الكومة الثنائية شجرة بيانات ثنائية كاملة، فإنّ من السهل تمثيلها بواسطة مصفوفة وطريقة التمثيل هذه فعالة من ناحية المساحة المستهلكة. إن كانت العقدة الأب مخزونة في الموقع i فيمكن حينئذٍ حساب موقع الابن الأيسر عن طريق العلاقة ‎2 * i + 1 والابن الأيمن عن طريق العلاقة ‎2 * i + 2. (على فرض أنّ حساب المواقع يبدأ من 0).

خطوات الخوارزمية

1. إنشاء كومة عظمى max heap من البيانات المدخلة.
2. يخزّن العنصر الأكبر كجذر للكومة، ثم يستبدل بالعنصر الأخير في الكومة ويتبع ذلك تقليل حجم الكومة بمقدار واحد، وفي النهاية نجرية عملية heapify على جذر الشجرة.
3. تكرار الخطوات السابقة ما دام حجم الكومة أكبر من 1.

بناء الكومة

لا يمكن تطبيق عملية بناء الكومة Heapify على عقدة إلا إذا أجريت هذه العملية على العقد الأبناء؛ لذا يجب إجراء عملية بناء الكومة من الأسفل إلى الأعلى.

يمكن توضيح ذلك بالمخطط التالي:

Input data: 4, 10, 3, 5, 1
         4(0)
        /   \
     10(1)   3(2)
    /   \
 5(3)    1(4)

تمثل الأرقام المحاطة بالأقواس مواقع العناصر في المصفوفة 

تطبيق عملية إنشاء الكومة في الموقع 1
         4(0)
        /   \
    10(1)    3(2)
    /   \
5(3)    1(4)

تطبيق عملية إنشاء الكومة في الموقع 0
        10(0)
        /  \
     5(1)  3(2)
    /   \
 4(3)    1(4)

تستدعي عملية إنشاء الكومة نفسها تعاوديًا لبناء الكومة من الأعلى إلى الأسفل

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية الترتيب بالكومة في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 

using namespace std; 

// i تبني الدالة كومة من شجرة فرعية جذرها العقدة 
// والتي تمثّل موقعًا في المصفوفة المعطاة
// n : حجم الكومة
void heapify(int arr[], int n, int i) 
{ 
	int largest = i; // تهيئة الجذر
	int l = 2*i + 1; // 2*i + 1 = اليسار
	int r = 2*i + 2; // 2*i + 2 = اليمين

	// إن كان الابن الأيسر أكبر من الجذر 
	if (l < n && arr[l] > arr[largest]) 
		largest = l; 

	// إن كان الجذر الأيمن أكبر من أكبر عنصر لحد الآن
	if (r < n && arr[r] > arr[largest]) 
		largest = r; 

	// إن لم يكن العنصر الأكبر هو الجذر
	if (largest != i) 
	{ 
		swap(arr[i], arr[largest]); 

		// بناء الكومة تعاوديًا من المصفوفة الجزئية المعنية
		heapify(arr, n, largest); 
	} 
} 

// الدالة المسؤولة عن عملية الترتيب بالكومة
void heapSort(int arr[], int n) 
{ 
	// بناء الكومة
	for (int i = n / 2 - 1; i >= 0; i--) 
		heapify(arr, n, i); 

	// استخراج العناصر من الكومة واحدًا تلو الآخر
	for (int i=n-1; i>=0; i--) 
	{ 
		// تحريك الجذر الحالي إلى النهاية
		swap(arr[0], arr[i]); 

		// استدعاء الدالة على المصفوفة المتبقية
		heapify(arr, i, 0); 
	} 
} 

/* دالة مساعدة لطباعة عناصر المصفوفة */
void printArray(int arr[], int n) 
{ 
	for (int i=0; i<n; ++i) 
		cout << arr[i] << " "; 
	cout << "\n"; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	int arr[] = {12, 11, 13, 5, 6, 7}; 
	int n = sizeof(arr)/sizeof(arr[0]); 

	heapSort(arr, n); 

	cout << "Sorted array is \n"; 
	printArray(arr, n); 
}

• بايثون:

# i تحول الدالة شجرة فرعية إلى كومة جذرها في الموقع
# n حجم الكومة هو 
def heapify(arr, n, i): 
	largest = i # تهيئة هذا المتغير ليكون الجذر
	l = 2 * i + 1	 # 2*i + 1 = اليسار
	r = 2 * i + 2	 # 2*i + 2 = اليمين

	# التحقق من أنّ عقدة الابن الأيسر للجذر موجودة
    # وأنّ قيمتها أكبر من قيمة عقدة الجذر
	if l < n and arr[i] < arr[l]: 
		largest = l 

	# التحقق من أنّ عقدة الابن الأيمن للجذر موجودة
    # وأنّ قيمتها أكبر من قيمة عقدة الجذر
	if r < n and arr[largest] < arr[r]: 
		largest = r 

	# تغيير الجذر إن تطلب الأمر ذلك
	if largest != i: 
		arr[i],arr[largest] = arr[largest],arr[i] # إجراء التبديل

		# إنشاء كومة من الجذر
		heapify(arr, n, largest) 

# الدالة الرئيسة التي ترتب عناصر المصفوفة ذات الحجم المعطى
def heapSort(arr): 
	n = len(arr) 

	# بناء كومة عظمى
	for i in range(n, -1, -1): 
		heapify(arr, n, i) 

	# استخراج العناصر واحدًا تلو الآخر
	for i in range(n-1, 0, -1): 
		arr[i], arr[0] = arr[0], arr[i] # إجراء التبديل
		heapify(arr, i, 0) 

# اختبار الدوال السابقة
arr = [ 12, 11, 13, 5, 6, 7] 
heapSort(arr) 
n = len(arr) 
print ("Sorted array is") 
for i in range(n): 
	print ("%d" %arr[i]),

• جافا:

public class HeapSort 
{ 
	public void sort(int arr[]) 
	{ 
		int n = arr.length; 

		// بناء الكومة إعادة ترتيب المصفوفة
		for (int i = n / 2 - 1; i >= 0; i--) 
			heapify(arr, n, i); 

		// استخراج العناصر من الكومة واحدًا تلو الآخر
		for (int i=n-1; i>=0; i--) 
		{ 
			// تحريك الجذر الحالي إلى النهاية
			int temp = arr[0]; 
			arr[0] = arr[i]; 
			arr[i] = temp; 

			// استدعاء الدالة التالية على الكومة المختزلة
			heapify(arr, i, 0); 
		} 
	} 

	// i يحول التابع شجرة فرعية إلى كومة جذرها في الموقع
	// n حجم الكومة هو 
	void heapify(int arr[], int n, int i) 
	{ 
		int largest = i; // تهيئة المتغير ليكون الجذر
		int l = 2*i + 1; // 2*i + 1 = اليسار
		int r = 2*i + 2; // 2*i + 2 = اليمين 

		// إن كانت قيمة عقدة الابن الأيسر للجذر أكبر من الجذر
		if (l < n && arr[l] > arr[largest]) 
			largest = l; 

		// إن كانت قيمة عقدة الابن الأيمن أكبر من أكبر قيمة حتى الآن
		if (r < n && arr[r] > arr[largest]) 
			largest = r; 

		// إن لم تكن أكبر قيمة هي الجذر
		if (largest != i) 
		{ 
			int swap = arr[i]; 
			arr[i] = arr[largest]; 
			arr[largest] = swap; 

			// استدعاء الدالة تعاودية لتحويل الشجرة الفرعية المعطاة إلى كومة
			heapify(arr, n, largest); 
		} 
	} 

	/* تابع مساعد لطباعة عناصر المصفوفة المعطاة */
	static void printArray(int arr[]) 
	{ 
		int n = arr.length; 
		for (int i=0; i<n; ++i) 
			System.out.print(arr[i]+" "); 
		System.out.println(); 
	} 

	// اختبار التوابع السابقة
	public static void main(String args[]) 
	{ 
		int arr[] = {12, 11, 13, 5, 6, 7}; 
		int n = arr.length; 

		HeapSort ob = new HeapSort(); 
		ob.sort(arr); 

		System.out.println("Sorted array is"); 
		printArray(arr); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لعملية heapify المقدار O(Log n)‎، ويبلغ التعقيد الزمني لعملية إنشاء الكومة وبنائها المقدار O(n)‎؛ ولذلك يبلغ التعقيد الزمني لخوارزمية الترتيب بالكومة المقدار O(n Log n)‎.

تستخدم خوارزمية الترتيب بالكومة استخدامًا محدودًا لأنّ خوارزميتا الترتيب السريع والترتيب بالدمج أفضل من الناحية العمليّة.

مصادر

• صفحة Heap Sort في توثيق الخوارزميات في موقع GeeksforGeeks.