Algorithms/priority queues

يعدّ رتل الأولوية Priority Queue امتدادًا للرتل العادي ويمتلك الخصائص التالية:

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

في المثال التالي يمتلك العنصر ذو قيمة ASCII الأعلى الأولوية الأعلى.

يدعم رتل الأولوية العمليات التالية:

• insert(item, priority)‎: تضيف هذه العملية عنصرًا مع الأولوية المعطاة.
• getHighestPriority()‎: تعيد هذه العملية العنصر ذا الأولوية الأعلى.
• deleteHighestPriority()‎: تحذف هذه العملية العنصر ذا الأولوية الأعلى.

إنشاء رتل الأولوية

يمكن الاستفادة من المصفوفات Arrays والقوائم المترابطة Linked Lists والكومات Heaps لإنشاء رتل الأولوية.

إنشاء رتل الأولوية باستخدام المصفوفات

يمكن إنشاء رتل الأولوية باستخدام المصفوفات التي تتخذ البنية التالية:

struct item {
   int item;
   int priority;
}

يمكن تنفيذ العملية insert()‎ بإضافة عنصر في نهاية المصفوفة والتعقيد الزمني لهذه العملية هو O(1)‎.

ويمكن تنفيذ العملية getHighestPriority()‎ عن طريق البحث الخطّي عن العنصر الذي يمتلك الأولوية الأعلى في المصفوفة، والتعقيد الزمني لهذه العملية هو O(n)‎.

يمكن تنفيذ العملية deleteHighestPriority()‎ بالبحث الخطّي أولًا عن العنصر ثم حذفه وتحريك جميع العناصر التي تليه خطوة إلى الوراء.

إنشاء رتل الأولوية باستخدام القوائم المترابطة

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

إنشاء رتل الأولوية باستخدام الكومات

يُفضل استخدام الكومات عادة في إنشاء رتل الأولوية وذلك لأنّ الكومات تتفوق من ناحية الأداء على المصفوفات والقوائم المترابطة، ففي الكومات الثنائية Binary Heap يكون التعقيد الزمني للعملية getHighestPriority()‎ هو O(1)‎ والعملية insert()‎ هو O(Logn)‎ والعملية deleteHighestPriority()‎ هو O(Logn)‎.

أما في كومات فابيوناتشي Fabionacci Heap فالتعقيد الزمني الاستهلاكي amortized للعمليتين insert()‎ و getHighestPriority()‎ هو O(1)‎ والعملية deleteHighestPriority()‎ هو O(Logn)‎.

تطبيقات على رتل الأولوية

1. جدولة وحدة المعالجة المركزية CPU.
2. الخوارزميات البيانية مثل خوارزمية Dijkstra’s shortest path و Prim’s minimum spanning tree وغيرها.
3. جميع تطبيقات الأرتال حيث تكون الأولوية مطلوبة.

رتل الأولوية في لغة C++‎

تقدّم لغة C++‎ التوابع التالية للتعامل مع رتل الأولوية:

• priority_queue::empty()‎: يعيد هذا التابع نتيجة التحقق من كون الرتل فارغًا أو لا.
• priority_queue::size()‎: يعيد التابع حجم الرتل.
• priority_queue::top()‎: يعيد التابع إشارة reference إلى العنصر العلوي في الرتل.
• priority_queue::push(g)‎: يضيف التابع العنصر g إلى نهاية الرتل.
• priority_queue::pop()‎: يحذف التابع أول عنصر في الرتل.
• priority_queue::swap()‎: يُستخدم هذا التابع لتبديل محتويات رتل أولوية مع رتل أولوية آخر له نفس الحجم والنوع.
• priority_queue::emplace()‎: يُستخدم هذا التابع لإدراج عنصر جديد في رتل الأولوية، ويضاف العنصر الجديد إلى قمّة رتل الأولوية.
• priority_queue valu_type: يمثّل التابع نوع الكائن المخزّن كعنصر في رتل الأولوية، وهو نظير لمعامل القالب.

أمثلة

تعرض الشيفرة التالية طريقة التعامل مع رتل الأولوية في لغة C++‎:

#include <iostream> 
#include <queue> 

using namespace std; 

void showpq(priority_queue <int> gq) 
{ 
	priority_queue <int> g = gq; 
	while (!g.empty()) 
	{ 
		cout << '\t' << g.top(); 
		g.pop(); 
	} 
	cout << '\n'; 
} 

int main () 
{ 
	priority_queue <int> gquiz; 
	gquiz.push(10); 
	gquiz.push(30); 
	gquiz.push(20); 
	gquiz.push(5); 
	gquiz.push(1); 

	cout << "The priority queue gquiz is : "; 
	showpq(gquiz); 

	cout << "\ngquiz.size() : " << gquiz.size(); 
	cout << "\ngquiz.top() : " << gquiz.top(); 


	cout << "\ngquiz.pop() : "; 
	gquiz.pop(); 
	showpq(gquiz); 

	return 0; 
}

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

The priority queue gquiz is :     30    20    10    5    1

gquiz.size() : 5
gquiz.top() : 30
gquiz.pop() :     20    10    5    1

رتل الأولوية في بايثون

تستخدم الكومات Heaps عادة لتمثيل رتل الأولوية، وتقدم بايثون وحدة heapq للتعامل مع الكومات، وما يميّز هذا النوع من بنى المعطيات في بايثون هو أنّ أصغر عنصر في الكومة هو الذي يحذف دائمًا (min heap)، وأنّ اللغة تحافظ على بنية الكومة عند إضافة العناصر أو حذفها من الكومة، ويعيد التعبير heap[0]‎ العنصر الأصغر دائمًا.

العمليات التي يمكن إجراؤها على الكومة

• heapify(iterable)‎: تستخدم هذه الدالة لتحويل أي كائن قابل للتكرار iterable إلى كومة.
• heappush(heap, ele)‎: تستخدم هذه الدالة لإدراج العنصر المعطى في الكومة، ويجدر الانتباه إلى أنّه لن يحصل أي تغيير في بنية الكومة وسيعدل ترتيب العناصر وفقًا لذلك.
• heappop(heap)‎: تستخدم هذه الدالة لحذف وإعادة أصغر عنصر في الكومة، ويجدر الانتباه إلى أنّه لن يحصل أي تغيير في بنية الكومة وسيعدل ترتيب العناصر وفقًا لذلك.

يعرض المثال التالي طريقة استخدام هذه الدوال:

# استيراد الوحدة
import heapq 

# تهيئة القائمة
li = [5, 7, 9, 1, 3] 

# تحويل القائمة إلى كومة
heapq.heapify(li) 

# طباعة الكومة الناتجة من عملية التحويل
print ("The created heap is : ",end="") 
print (list(li)) 

# إضافة عنصر إلى الكومة
heapq.heappush(li,4) 

# طباعة الكومة بعد إضافة العنصر
print ("The modified heap after push is : ",end="") 
print (list(li)) 

# حذف أصغر عنصر في الكومة
print ("The popped and smallest element is : ",end="") 
print (heapq.heappop(li))

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

The created heap is : [1, 3, 9, 7, 5]
The modified heap after push is : [1, 3, 4, 7, 5, 9]
The popped and smallest element is : 1

• heappushpop(heap, ele)‎: تدمج هذه الدالة عمليتي الإضافة والحذف في جملة واحدة، ولن تتغير بنية الكومة بعد تنفيذ هذه الدالة.
• heapreplace(heap, ele)‎: تدرج هذه الدالة العنصر المعطى وتحذف عنصرًا من الكومة في جملة واحدة، ولكن تختلف هذه الدالة عن الدالة السابقة في أنّ العنصر يُحذف أولًا، ثم يضاف العنصر المعطى إلى الكومة، بمعنى أنّه يمكن إعادة قيمة أعلى من القيمة المضافة إلى الكومة.

# استيراد الوحدة
import heapq 

# تهيئة القائمة الأولى
li1 = [5, 7, 9, 4, 3] 

# تهيئة القائمة الثانية
li2 = [5, 7, 9, 4, 3] 

# تحويل القائمتين إلى كومتين
heapq.heapify(li1) 
heapq.heapify(li2) 

# إضافة عنصر وحذف آخر في نفس الوقت
print ("The popped item using heappushpop() is : ",end="") 
print (heapq.heappushpop(li1, 2)) 

# إضافة عنصر وحذف آخر في نفس الوقت
print ("The popped item using heapreplace() is : ",end="") 
print (heapq.heapreplace(li2, 2))

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

The popped item using heappushpop() is : 2
The popped item using heapreplace() is : 3

• nlargest(k, iterable, key = fun)‎: تستخدم هذه الدالة لإعادة k أكبر عناصر من الكائن القابل للتكرار المعطى والتي تطابق المفتاح المعطى.
• nsmallest(k, iterable, key = fun)‎: تستخدم هذه الدالة لإعادة k أصغر عناصر من الكائن القابل للتكرار المعطى والتي تطابق المفتاح المعطى.

# استيراد الوحدة
import heapq 

# تهيئة القائمة
li1 = [6, 7, 9, 4, 3, 5, 8, 10, 1] 

# تحويل القائمة إلى كومة
heapq.heapify(li1) 

# طباعة أكبر ثلاثة أعداد
# ستطبع الدالة الأعداد 10 و 9 و 8
print("The 3 largest numbers in list are : ",end="") 
print(heapq.nlargest(3, li1)) 

# طباعة أصغر ثلاثة أعداد
# ستطبع الدالة الأعداد 1 و 3 و 4
print("The 3 smallest numbers in list are : ",end="") 
print(heapq.nsmallest(3, li1))

المخرجات:

The 3 largest numbers in list are : [10, 9, 8]
The 3 smallest numbers in list are : [1, 3, 4]

رتل الأولوية في جافا

هناك بعض الأمور المهمة التي ينبغي الانتباه إليها عند التعامل مع رتل الأولوية في لغة جافا:

• لا يسمح الصنف PriorityQueue باستخدام مؤشرات NULL.
• لا يمكن إنشاء الصنف PriorityQueue من كائنات غير قابلة للمقارنة.
• الصنف PriorityQueue هو رتل غير مرتبط unbound.
• رأس هذا الرتل هو أصغر عنصر بالنسبة إلى الترتيب المحدد، وإن ارتبط أكثر من عنصر بالقيمة الصغرى، يكون الرأس أحد هذه العناصر، وتكسر الروابط عشوائيًا.
• تتعامل عمليات الاسترجاع poll و remove و peek و element مع العنصر الموجود في بداية الرتل.
• بعض توابع هذا الصنف موروثة من الأصناف AbstractQueue و AbstractCollection و Collenction و Object.

الدوال البانية للصنف PriorityQueue

• PriorityQueue()‎: تنشئ هذه الدالة البانية الصنف PriorityQueue وتعطيه السعة الابتدائية الافتراضية (11) وتُرتّب العناصر فيه حسب ترتيبها الطبيعي.
• PriorityQueue(Collection<E> c)‎: تنشئ هذه الدالة البانية الصنف PriorityQueue والذي يحتوي على العناصر الموجودة في المجموعة المحددة.
• PriorityQueue(int initialCapacity)‎: تنشئ هذه الدالة البانية الصنف PriorityQueue مع السعة الابتدائية المعطاة وتُرتّب العناصر فيه حسب ترتيبها الطبيعي.
• PriorityQueue(int initialCapcity, Comparator<E> comparator)‎ : تنشئ الدالة الصنف PriorityQueue مع السعة الابتدائية المعطاة وتُرتّب العناصر فيه بالاعتماد على المقارِن comparator المعطى.
• PriorityQeue(PriorityQeue<E> c)‎: تنشئ الدالة البانية الصنف PriorityQueue والذي يحتوي على العناصر الخاصة برتل الأولوية المعطى.
• PriorityQueue(SortedSet<E> c)‎: تنشئ الدالة البانية الصنف PriorityQueue والذي يحتوي على العناصر الخاصة بالمجموعة المرتبة المعطاة.

توابع الصنف PriorityQueue

يمتلك الصنف PriorityQueue التوابع التالية:

• boolean add(E element)‎: يُدرج هذا التابع العنصر المعطى في رتل الأولوية.
• public remove()‎: يحذف هذا التابع نسخة مفردة من العنصر المعطى من الرتل إن كان العنصر موجودًا.
• public poll()‎: يجلب هذا التابع ويحذف رأس الرتل، أو يعيد القيمة null إن كان الرتل فارغًا.
• public peek()‎: يجلب هذا التابع ولكن لا يحذف رأس الرتل أو يعيد القيمة null إن كان الرتل فارغًا.
• Iterator iterator()‎: يعيد التابع كائن تكرار يمرّ على جميع عناصر الرتل.
• boolean contains(Object o)‎: يعيد التابع القيمة true إن كانت العنصر المعطى موجودًا في الرتل.
• void clear()‎: يستخدم هذا التابع لحذف جميع محتويات رتل الأولوية.
• boolean offer(E e)‎: يستخدم هذا التابع لإدراج عنصر معيّن في رتل الأولوية.
• int size()‎: يستخدم هذا التابع لإعادة عدد العناصر الموجودة في المجموعة.
• toArray()‎: يستخدم هذا التابع لإعادة مصفوفة تتضمّن جميع العناصر في الرتل.
• Comparator comparator()‎: يستخدم هذا التابع لإعادة المقارِن الذي يمكن استخدامه لترتيب العناصر في الرتل.

أمثلة

تعرض الشيفرة التالية طريقة إنشاء رتل الأولوية والتعامل معه باستخدام لغة جافا:

import java.util.*; 

class Example 
{ 
	public static void main(String args[]) 
	{ 
		// إنشاء رتل أولوية فارغ
		PriorityQueue<String> pQueue = 
						new PriorityQueue<String>(); 

		// إضافة العناصر إلى رتل الأولوية
		pQueue.add("C"); 
		pQueue.add("C++"); 
		pQueue.add("Java"); 
		pQueue.add("Python"); 

		// طباعة العنصر ذي الأولوية الأعلى 
		System.out.println("Head value using peek function:"
										+ pQueue.peek()); 

		// طباعة جميع العناصر 
		System.out.println("The queue elements:"); 
		Iterator itr = pQueue.iterator(); 
		while (itr.hasNext()) 
			System.out.println(itr.next()); 

		// حذف العنصر ذي الأولوية الأعلى 
		// وطباعة رتل الأولوية الناتج 
		pQueue.poll(); 
		System.out.println("After removing an element" + 
						"with poll function:"); 
		Iterator<String> itr2 = pQueue.iterator(); 
		while (itr2.hasNext()) 
			System.out.println(itr2.next()); 

		// Java حذف العنصر الذي يحمل القيمة
		pQueue.remove("Java"); 
		System.out.println("after removing Java with" + 
						" remove function:"); 
		Iterator<String> itr3 = pQueue.iterator(); 
		while (itr3.hasNext()) 
			System.out.println(itr3.next()); 

		// التحقق من وجود عنصر معين
		boolean b = pQueue.contains("C"); 
		System.out.println ( "Priority queue contains C " + 
							"or not?: " + b); 

		// الحصول على الكائنات من الرتل
         // ووضعها في مصفوفة وطباعتها
		Object[] arr = pQueue.toArray(); 
		System.out.println ( "Value in array: "); 
		for (int i = 0; i<arr.length; i++) 
		System.out.println ( "Value: " + arr[i].toString()) ; 
	} 
}

المصادر

• صفحة Priority Queue | Set 1 (Introduction)‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Priority Queue in C++ Standard Template Library في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة Heap queue (or heapq) in Python في توثيق بنى المعطيات في موقع GeeksforGeeks.
• صفحة PriorityQueue in Java في توثيق بنى المعطيات في موقع GeeksforGeeks.