Algorithms/binary heaps

الكومة الثنائية هي شجرة بيانات ثنائية تمتلك الخصائص التالية:

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

تمثيل الكومة الثنائية

تستخدم المصفوفات عادة في تمثيل الكومات الثنائية، حيث يكون الجذر في الموقع Arr[0]‎، ويمكن الوصول إلى عقدة معينة حسب الجدول التالي:

التعبير	القيمة المعادة
Arr[(i-1)/2]‎	العقدة الأب
Arr[(2*i)+1]‎	عقدة الابن الأيسر
Arr[(2*i)+2]‎	عقدة الابن الأيمن

تستخدم طريقة ترتيب المستوى Level Order لتمثيل الكومة الثنائية في مصفوفة.

تطبيقات على الكومات

1. ترتيب الكومة: تستخدم خوارزمية الترتيب بالكومة Heap Sort الكومات الثنائية لترتيب مصفوفة بتعقيد زمني يبلغ O(nLogn)‎.
2. رتل الأولوية: يمكن إنشاء رتل الأولوية Priority queue بطريقة فعالة وباستخدام الكومات الثنائية؛ وذلك لأنّها تدعم عمليات insert()‎ و delete()‎ و extractmax()‎ و decreaseKey()‎ وبتعقيد زمني يبلغ O(Logn)‎. وهناك أشكال أخرى من الكومات الثنائية مثل الكومة ثنائية الحد Binomial وكومة فابيوناتشي وتنفّذ هذه الكومات عملية الدمج union بكفائة عالية.
3. الخوارزميات البيانية: تستخدم أرتال الأولوية بصورة خاصة في الخوارزميات البيانية مثل خوارزمية ديكسترا للعثور على المسار الأقصر وخوارزمية برم للشجرة المولدة الأصغرية Prim's Minimum Spanning Tree.
4. يمكن حل العديد من المشاكل بكفاءة عالية باستخدام الكومات، مثل العثور على أكبر K عنصر في مصفوفة، وترتيب مصفوفة مرتّبة تقريبًا ودمج عدد معين من المصفوفات المرتبة.

العمليات الخاصة بالكومات الصغرى

1. getMini()‎: تعيد هذه العملية جذر الكومة الصغرى. يبلغ التعقيد الزمني لهذه العملية O(1).
2. extractMin()‎: تزيل هذه العملية أصغر عنصر في الكومة الصغرى. يبلغ التعقيد الزمني لهذه العملية O(Logn)‎ لأنّها بحاجة إلى المحافظة على خاصية الكومة (عن طريق استدعاء العملية heapify()‎ بعد إزالة الجذر.
3. decreaseKey()‎: تنقص هذه العملية قيمة المفتاح، ويبلغ التعقيد الزمني لهذه العملية O(Logn)‎. إن كانت القيمة التي تم إنقاصها أكبر من العقدة الأب فلن يكون هناك حاجة لفعل أي شيء، ولكن إن حصل العكس فسنحتاج إلى الانتقال إلى الأعلى لإصلاح الخلل الحاصل في بنية الكومة.
4. insert()‎: تدرج العملية مفتاحًا جديدًا في الكومة، ويبلغ التعقيد الزمني لهذه العملية O(Logn)‎. يُضاف المفتاح الجديد في نهاية الشجرة، وإن كان المفتاح الجديد أكبر من مفتاح عقدة الأب، فلن يكون هناك حاجة لفعل أي شيء، ولكن إن كان المفتاح الجديد أصغر فسنحتاج إلى الانتقال إلى الأعلى لإصلاح الخلل الحاصل في بنية الكومة.
5. delete()‎: يبلغ التعقيد الزمني لعملية الحذف O(Logn)‎ أيضًا. تستبدل العملية المفتاح المراد حذف بقيمة سالب ما لا نهاية وذلك باستدعاء العملية decreaseKey()‎، بعد ذلك يجب أن تصل قيمة سالب ما لا نهاية إلى الجذر؛ لذا تُستدعى العملية extractMin()‎ لإزالة المفتاح.

أمثلة

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

• C++‎:

#include<iostream> 
#include<climits> 
using namespace std; 

// نموذج لدالة مساعدة للتبديل بين عددين صحيحين
void swap(int *x, int *y); 

// صنف لتمثيل الكومة الصغرى
class MinHeap 
{ 
	int *harr; // مؤشر إلى مصفوفة من العناصر في الكومة 
	int capacity; // أقصى حجم ممكن للكومة الصغرى 
	int heap_size; // عدد العناصر الحالي في الكومة الصغرى 
public: 
	// دالة بانية
	MinHeap(int capacity); 

	// تحويل شجرة فرعية مع جذر إلى كومة في الموقع المعطى 
	void MinHeapify(int ); 

	int parent(int i) { return (i-1)/2; } 

	// i الحصول على موقع الابن الأيسر للعقدة في الموقع  
    to get index of left child of node at index i 
	int left(int i) { return (2*i + 1); } 

	// i الحصول على موقع الابن الأيمن للعقدة في الموقع
	int right(int i) { return (2*i + 2); } 

	// نستخرج الجذر الذي يحمل العنصر الأصغر
	int extractMin(); 

	// إنقاص قيمة المفتاح في الموقع المعطى إلى القيمة المحددة
	void decreaseKey(int i, int new_val); 

	// إعادة المفتاح الأدنى (مفتاح الجذر) من الكومة الصغرى
	int getMin() { return harr[0]; } 

	// حذف المفتاح المخزّن في الموقع المعطى
	void deleteKey(int i); 

	// إدراج المفتاح الجديد
	void insertKey(int k); 
}; 

// الدالة البانية: تبني هذه الدالة كومة من المصفوفة المعطى وبالحجم المعطى
MinHeap::MinHeap(int cap) 
{ 
	heap_size = 0; 
	capacity = cap; 
	harr = new int[cap]; 
} 

// إدراج مفتاح جديد في الكومة
void MinHeap::insertKey(int k) 
{ 
	if (heap_size == capacity) 
	{ 
		cout << "\nOverflow: Could not insertKey\n"; 
		return; 
	} 

	// أولًا ندرج المفتاح الجديد في نهاية الشجرة
	heap_size++; 
	int i = heap_size - 1; 
	harr[i] = k; 

	// معالجة أي خلل قد يحصل في بنية الكومة الصغرى
	while (i != 0 && harr[parent(i)] > harr[i]) 
	{ 
	swap(&harr[i], &harr[parent(i)]); 
	i = parent(i); 
	} 
} 

// إنقاص قيمة المفتاح في الموقع المعطى إلى القيمة المعطاة
// سنفترض أنّ القيمة الجديدة المعطاة أصغر من قيمة العنصر المحدد في المصفوفة
void MinHeap::decreaseKey(int i, int new_val) 
{ 
	harr[i] = new_val; 
	while (i != 0 && harr[parent(i)] > harr[i]) 
	{ 
	swap(&harr[i], &harr[parent(i)]); 
	i = parent(i); 
	} 
} 

// يحذف هذا التابع العنصر الأصغر (أو الجذر) من الكومة الصغرى
int MinHeap::extractMin() 
{ 
	if (heap_size <= 0) 
		return INT_MAX; 
	if (heap_size == 1) 
	{ 
		heap_size--; 
		return harr[0]; 
	} 

	// تخزين القيمة الصغرى ثم حذفها من الكمة
	int root = harr[0]; 
	harr[0] = harr[heap_size-1]; 
	heap_size--; 
	MinHeapify(0); 

	return root; 
} 


// تحذف هذه الدالة المفتاح في الموقع المحدد. تُنقص قيمة المفتاح إلى سالب ما لا نهاية، ثم تُستدعى العملية
// extractMin()
void MinHeap::deleteKey(int i) 
{ 
	decreaseKey(i, INT_MIN); 
	extractMin(); 
} 

// تابع تعاودي لتحويل شجرة فرعية إلى كومة مع الجذر الذي يكون في الموقع المعطى.
// يفترض هذا التوبع أنّ الأشجار الفرعية قد حُوّلت إلى كومات مسبقًا
void MinHeap::MinHeapify(int i) 
{ 
	int l = left(i); 
	int r = right(i); 
	int smallest = i; 
	if (l < heap_size && harr[l] < harr[i]) 
		smallest = l; 
	if (r < heap_size && harr[r] < harr[smallest]) 
		smallest = r; 
	if (smallest != i) 
	{ 
		swap(&harr[i], &harr[smallest]); 
		MinHeapify(smallest); 
	} 
} 

// دالة مساعدة للتبديل بين عنصرين
void swap(int *x, int *y) 
{ 
	int temp = *x; 
	*x = *y; 
	*y = temp; 
} 

// اختبار الدوال السابقة
int main() 
{ 
	MinHeap h(11); 
	h.insertKey(3); 
	h.insertKey(2); 
	h.deleteKey(1); 
	h.insertKey(15); 
	h.insertKey(5); 
	h.insertKey(4); 
	h.insertKey(45); 
	cout << h.extractMin() << " "; 
	cout << h.getMin() << " "; 
	h.decreaseKey(2, 1); 
	cout << h.getMin(); 
	return 0; 
}

• بايثون:

# استيراد دوال التعامل مع الكومات من مكتبة بايثون القياسية
from heapq import heappush, heappop, heapify 

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

# صنف لتمثيل الكومة الصغرى
class MinHeap: 
	
	# دالة بانية لتهيئة الكومة
	def __init__(self): 
		self.heap = [] 

	def parent(self, i): 
		return (i-1)/2
	
	# إدراج مفتاح جديد في الكومة
	def insertKey(self, k): 
		heappush(self.heap, k)		 

    # إنقاص قيمة المفتاح في الموقع المعطى إلى القيمة الجديدة المعطاة
    # يفترض التابع أنّ القيمة الجديدة المعطاة أصغر من قيمة العنصر في المصفوفة
	def decreaseKey(self, i, new_val): 
		self.heap[i] = new_val 
		while(i != 0 and self.heap[self.parent(i)] > self.heap[i]): 
			# استبدال heap[i]
            # إلى heap[parent(i)]
			self.heap[i] , self.heap[self.parent(i)] = ( 
			self.heap[self.parent(i)], self.heap[i]) 
			
	# يحذف التابع أصغر عنصر من الكومة الصغرى
	def extractMin(self): 
		return heappop(self.heap) 

	# يحذف التابع المفتاح في الموقع المعطى.يُنقص التابع في البداية قيمة المفتاح
    # extractMin() إلى سالب ما لا نهاية ثم يُستدعى التابع
	def deleteKey(self, i): 
		self.decreaseKey(i, float("-inf")) 
		self.extractMin() 

	# الحصول على أصغر عنصر في الكومة
	def getMin(self): 
		return self.heap[0] 

# اختبار التوابع السابقة
heapObj = MinHeap() 
heapObj.insertKey(3) 
heapObj.insertKey(2) 
heapObj.deleteKey(1) 
heapObj.insertKey(15) 
heapObj.insertKey(5) 
heapObj.insertKey(4) 
heapObj.insertKey(45) 

print heapObj.extractMin(), 
print heapObj.getMin(), 
heapObj.decreaseKey(2, 1) 
print heapObj.getMin()

تعطي الشيفرة السابقة المخرجات التالية:

2 4 1

مصادر

• صفحة heap في توثيق بنى المعطيات في موقع GeeksforGeeks.