عرض مصدر Algorithms/priority queues

<noinclude>{{DISPLAYTITLE:رتل الأولوية}}</noinclude>
يعدّ رتل الأولوية Priority Queue امتدادًا [[Algorithms/queues|للرتل]] العادي ويمتلك الخصائص التالية: 

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

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

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

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

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

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

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

يمكن إنشاء رتل الأولوية باستخدام المصفوفات التي تتخذ البنية التالية:<syntaxhighlight lang="text">
struct item {
   int item;
   int priority;
}
</syntaxhighlight>يمكن تنفيذ العملية <code>insert()‎</code> بإضافة عنصر في نهاية المصفوفة والتعقيد الزمني لهذه العملية هو <code>O(1)‎</code>.

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

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

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

يمكن استخدام [[Algorithms/linked lists|القوائم المترابطة]] لإنشاء رتل الأولوية، ولن يؤدي استخدام القوائم المترابطة إلى أي تغيير في التعقيد الزمني للعمليات المرتبطة بأرتال الأولوية، ولكن تتفوق [[Algorithms/linked lists|القوائم المترابطة]] على المصفوفات عند تنفيذ العملية <code>()deleteHighestPriority</code> حيث تصبح هذه العملية أكثر فعّالية لأنّنا لن نكون بحاجة إلى تحريك العناصر كما هو الحال مع المصفوفات.

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

يُفضل استخدام [[Algorithms/heaps|الكومات]] عادة في إنشاء رتل الأولوية وذلك لأنّ الكومات تتفوق من ناحية الأداء على [[Algorithms/arrays|المصفوفات]] و<nowiki/>[[Algorithms/linked lists|القوائم المترابطة]]، ففي الكومات الثنائية Binary Heap يكون التعقيد الزمني للعملية <code>getHighestPriority()‎</code> هو <code>O(1)‎</code> والعملية <code>insert()‎</code> هو <code>O(Logn)‎</code> والعملية <code>deleteHighestPriority()‎</code> هو <code>O(Logn)‎</code>.

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

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

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

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

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

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

=== أمثلة ===

تعرض الشيفرة التالية طريقة التعامل مع رتل الأولوية في لغة C++‎:<syntaxhighlight lang="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; 
} 

</syntaxhighlight>تعطي الشيفرة السابقة المخرجات التالية:<syntaxhighlight lang="text">
The priority queue gquiz is :     30    20    10    5    1

gquiz.size() : 5
gquiz.top() : 30
gquiz.pop() :     20    10    5    1
</syntaxhighlight>

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

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

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

* <code>[[Python/heapq/heapify|heapify(iterable)‎]]</code>: تستخدم هذه الدالة لتحويل أي كائن قابل للتكرار iterable إلى كومة.
* <code>[[Python/heapq/heappush|heappush(heap, ele)]]‎</code>: تستخدم هذه الدالة لإدراج العنصر المعطى في الكومة، ويجدر الانتباه إلى أنّه لن يحصل أي تغيير في بنية الكومة وسيعدل ترتيب العناصر وفقًا لذلك.
* <code>[[Python/heapq/heappop|heappop(heap)‎]]</code>: تستخدم هذه الدالة لحذف وإعادة أصغر عنصر في الكومة، ويجدر الانتباه إلى أنّه لن يحصل أي تغيير في بنية الكومة وسيعدل ترتيب العناصر وفقًا لذلك.

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

<source lang="python"># استيراد الوحدة
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)) 
</source>
تعطي الشيفرة السابقة المخرجات التالية:<syntaxhighlight lang="text">
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
</syntaxhighlight>
* <code>[[Python/heapq/heappushpop|heappushpop(heap, ele)]]‎</code>: تدمج هذه الدالة عمليتي الإضافة والحذف في جملة واحدة، ولن تتغير بنية الكومة بعد تنفيذ هذه الدالة.
* <code>[[Python/heapq/heapreplace|heapreplace(heap, ele)‎]]</code>: تدرج هذه الدالة العنصر المعطى وتحذف عنصرًا من الكومة في جملة واحدة، ولكن تختلف هذه الدالة عن الدالة السابقة في أنّ العنصر يُحذف أولًا، ثم يضاف العنصر المعطى إلى الكومة، بمعنى أنّه يمكن إعادة قيمة أعلى من القيمة المضافة إلى الكومة.

<source lang="python"># استيراد الوحدة
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)) 
</source>
تعطي الشيفرة السابقة المخرجات التالية:<syntaxhighlight lang="text">
The popped item using heappushpop() is : 2
The popped item using heapreplace() is : 3
</syntaxhighlight>
* <code>[[Python/heapq/nlargest|nlargest(k, iterable, key = fun)‎]]</code>: تستخدم هذه الدالة لإعادة <code>k</code> أكبر عناصر من الكائن القابل للتكرار المعطى والتي تطابق المفتاح المعطى.
* <code>[[Python/heapq/nsmallest|nsmallest(k, iterable, key = fun)]]‎</code>: تستخدم هذه الدالة لإعادة <code>k</code> أصغر عناصر من الكائن القابل للتكرار المعطى والتي تطابق المفتاح المعطى.

<source lang="python"># استيراد الوحدة
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)) 
</source>
المخرجات:<syntaxhighlight lang="text">
The 3 largest numbers in list are : [10, 9, 8]
The 3 smallest numbers in list are : [1, 3, 4]
</syntaxhighlight>
== رتل الأولوية في جافا ==

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

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

=== الدوال البانية للصنف <code>PriorityQueue</code> ===

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

=== توابع الصنف <code>PriorityQueue</code> ===

يمتلك الصنف <code>PriorityQueue</code> التوابع التالية:

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

=== أمثلة ===

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

<source lang="java">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()) ; 
	} 
} </source>

== انظر أيضًا ==
*[[Algorithms/queues|الأرتال]]
*[[Algorithms/circular queues|الأرتال الدائرية]]
== المصادر ==

* صفحة [https://www.geeksforgeeks.org/priority-queue-set-1-introduction/ Priority Queue | Set 1 (Introduction)]‎ في توثيق بنى المعطيات في موقع GeeksforGeeks.
* صفحة [https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/ Priority Queue in C++ Standard Template Library] في توثيق بنى المعطيات في موقع GeeksforGeeks.
* صفحة [https://www.geeksforgeeks.org/heap-queue-or-heapq-in-python/ Heap queue (or heapq) in Python] في توثيق بنى المعطيات في موقع GeeksforGeeks.
* صفحة [https://www.geeksforgeeks.org/priority-queue-class-in-java-2/ PriorityQueue in Java] في توثيق بنى المعطيات في موقع GeeksforGeeks.

[[تصنيف: الخوارزميات]]
[[تصنيف: بنى المعطيات]]
[[تصنيف:الأرتال]]