طابور أولويات جافا

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

طابور الأولويات في جافا

الفئة java.util.PriorityQueue توفر لنا تنفيذًا لهذا النوع من البيانات، باستخدام تنفيذ الهيكل الرئيسي للأولويات داخليًا. طابور الأولويات في جافا هو طابور غير محدد الحجم. تم إدخاله في جافا 1.5 وتحسينه في إصدار جافا SE 8. يتم تنفيذ طابور الأولويات داخليًا باستخدام هيكل بيانات “الهرم الأولويات”. إليك تسلسل الفئات لطابور الأولويات: الرسم البياني لفئة طابور الأولويات:

بناة طابور الأولويات في جافا

1. PriorityQueue() – ينشئ طابور الأولويات بالسعة الافتراضية، أي 11
2. PriorityQueue(Collection c) – ينشئ طابور الأولويات باستخدام العناصر في المجموعة المحددة
3. PriorityQueue(int initialCapacity) – ينشئ PriorityQueue بالسعة الأولية المحددة
4. PriorityQueue(int initialCapacity, Comparator comparator) – ينشئ PriorityQueue بالسعة الأولية المحددة وترتيب عناصره وفقًا للمقارن المحدد
5. PriorityQueue(PriorityQueue c) – ينشئ PriorityQueue يحتوي على العناصر في طابور الأولويات المحدد
6. PriorityQueue(SortedSet c) – ينشئ PriorityQueue يحتوي على العناصر في مجموعة مرتبة المحددة

يتم ترتيب عناصر طابور الأولويات بترتيبها الطبيعي ما لم نوفر Comparator أثناء إنشائه. تكون العناصر مرتبة ترتيبًا تصاعديًا افتراضيًا، لذلك يكون رأس الطابور هو العنصر الذي يكون أولويته الأقل. إذا كان هناك عنصران مؤهلان ليصبحا رأسًا في نفس الوقت، يتم حل مثل هذه العقد بشكل تعسفي.

مثال على Java PriorityQueue

لنقم بإنشاء PriorityQueue، يحتوي على مهام مختلفة:

PriorityQueue tasks=new PriorityQueue();
tasks.add("task1");
tasks.add("task4");
tasks.add("task3");
tasks.add("task2");
tasks.add("task5");

هذا ينشئ PriorityQueue من المهام، والتي ستكون مرتبة وفقًا للترتيب الطبيعي لـ String. لنقم بإنشاء PriorityQueue آخر يرتب المهام بترتيب عكسي للترتيب الطبيعي. لذلك نحتاج إلى تمرير مقارنًا:

PriorityQueue reverseTasks=new PriorityQueue(Comparator.reverseOrder());
reverseTasks.add("task1");
reverseTasks.add("task4");
reverseTasks.add("task3");
reverseTasks.add("task2");
reverseTasks.add("task5");

طرق PriorityQueue في جافا

الآن، دعنا نلقي نظرة على جميع الطرق المتاحة لـ PriorityQueue ونستخدمها:

1. Boolean add(E e) – هذه الطريقة تقوم بإدراج العنصر المحدد في الطابور. لقد قمنا بإضافة 5 مهام بالفعل في طابورنا باستخدام هذه الطريقة.

2. Comparator comparator() – هذه الطريقة تقوم بإرجاع المقارن المستخدم لترتيب العناصر في هذا الطابور. تُرجع قيمة null إذا لم يتم تحديد مقارن وكان الطابور مرتبًا وفقًا للترتيب الطبيعي لعناصره. لذلك، إذا فعلنا:

   System.out.println(tasks.comparator());
   System.out.println(reverseTasks.comparator());
   

   سيكون الإخراج:

   null
   java.util.Collections$ReverseComparator@15db9742
   

3. boolean contains(Object o) – تعيد قيمة صحيحة إذا كانت الطابور يحتوي على العنصر المحدد. دعونا نتحقق مما إذا كان “task3” ينتمي إلى طابور الأولويات tasks:

   System.out.println(tasks.contains("task3"));
   

   يطبع هذا:

   true
   

4. boolean offer(E e) – تضيف هذه الطريقة، تمامًا مثل طريقة add()، عنصرًا إلى الطابور. طريقة offer() وطريقة add() في الواقع مختلفتان قليلاً بالنسبة للطوابير ذات السعة المحددة، ولكن في حالة PriorityQueue، كلتاهما متشابهتان. على عكس add()، لا تقوم offer() بإلقاء استثناء حتى إذا فشلت في إضافة العنصر إلى الطابور.

5. E peek() – يسترجع رأس هذا الطابور، أو يعيد قيمة فارغة إذا كان الطابور فارغًا. بعبارة أخرى، يُرجع العنصر ذو الأولوية الأعلى. لذا، الشيفرة التالية:

   System.out.println(tasks.peek());
   System.out.println(reverseTasks.peek());
   

   تُعيد لنا:

   task1
   task5
   

6. تصفية E() – تسترجع هذه الطريقة أيضًا رأس الطابور (العنصر ذو أعلى أولوية)، أو تُرجع قيمة فارغة إذا كان الطابور فارغًا. ولكن على عكس peek()، فإنها أيضًا تقوم بإزالة العنصر. لذا، إذا قمنا بالاتصال بـ poll():

   System.out.println("استفتاء على المهام: "+tasks.poll());
   System.out.println("استفتاء على عكس المهام: "+reverseTasks.poll());
   

   ثم انظر:

   System.out.println("التطلع إلى المهام: "+tasks.peek());
   System.out.println("التطلع إلى عكس المهام: "+reverseTasks.peek());
   

   سنحصل على الناتج التالي:

   استفتاء على المهام: مهمة 1
   استفتاء على عكس المهام: مهمة 5
   التطلع إلى المهام: مهمة 2
   التطلع إلى عكس المهام: مهمة 4
   

7. int size() – تُرجع عدد العناصر في الطابور.

8. boolean remove(Object o) – تقوم بإزالة العنصر المحدد من الطابور، إذا كان موجودًا. إذا كان هناك عناصر متشابهة، فإنها تزيل فقط واحدة منها.

9. Object[] toArray() – تُرجع مصفوفة تحتوي على جميع العناصر في الطابور.

10. T[] toArray(T[] a) – يعيد مصفوفة تحتوي على جميع العناصر في الطابور، ونوع المصفوفة المعادة هو نفس نوع المصفوفة المحدد.

11. Iterator iterator() – يعيد محددًا للطابور.

12. void clear() – يزيل جميع العناصر من الطابور.

بالإضافة إلى ذلك، تورث PriorityQueue أيضًا الطرق من فئات Collection و Object.

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

1. بالنسبة لطرق الإضافة والإزالة، تعقيد الزمن هو O(log(n))
2. بالنسبة لطرق الإزالة(Object) والبحث(Object)، تعقيد الزمن هو خطي
3. بالنسبة لطرق الاسترجاع، لديه تعقيد زمني ثابت

هذا التنفيذ لطابور الأولويات غير آمن للتعامل مع الخيوط. لذا، إذا كنا بحاجة إلى وصول متزامن، يجب علينا استخدام PriorityBlockingQueue. المرجع: وثائق الواجهة البرمجية للتطبيقات