قائمة انتظار أولوية Java: ليست قائمة انتظار كلاسيكية

في هذه المقالة، سنتعرف على قائمة الانتظار ذات الأولوية، فئة Java، التي تنفذ واجهة قائمة الانتظار. ماذا يعرف المبرمج عن واجهة الانتظار العادية؟ بداية، تعتمد هذه الواجهة على مبدأ FIFO أو "ما يدخل أولاً يخرج أولاً". وهذا يذكرنا بقائمة الانتظار العادية بمعناها الشائع. هل تريد الحصول على القهوة من ماك درايف؟ إذا كانت سيارتك هي الأولى بالقرب من النافذة، فسوف تحصل على قهوتك قبل السائق الذي يليك.

إعلان واجهة قائمة الانتظار

public interface Queue<E> extends Collection<E>

ما هي قائمة الانتظار ذات الأولوية

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

منشئو فئة PriorityQueue والإعلان

توفر فئة PriorityQueue 6 طرق مختلفة لإنشاء قائمة انتظار ذات أولوية في Java.

• PriorityQueue() - قائمة انتظار فارغة ذات سعة أولية افتراضية (11) تقوم بترتيب عناصرها وفقًا لترتيبها الطبيعي.
• PriorityQueue(Collection c) - قائمة انتظار فارغة تحتوي على العناصر الموجودة في المجموعة المحددة.
• PriorityQueue(int originalCapacity) - قائمة انتظار فارغة ذات سعة أولية محددة تقوم بترتيب عناصرها وفقًا لترتيبها الطبيعي.
• PriorityQueue(int originalCapacity, Comparator comparator) - قائمة انتظار فارغة ذات سعة أولية محددة تقوم بترتيب عناصرها وفقًا للمقارنة المحددة.
• PriorityQueue(PriorityQueue c) - قائمة انتظار فارغة تحتوي على العناصر الموجودة في قائمة انتظار الأولوية المحددة.
• PriorityQueue(SortedSet c) - قائمة انتظار فارغة تحتوي على العناصر الموجودة في المجموعة المصنفة المحددة.

يتم الإعلان عن قائمة انتظار الأولوية في Java بالطريقة التالية:

public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable

إنشاء قائمة انتظار الأولوية

لنقم بإنشاء قائمة انتظار ذات أولوية للأعداد الصحيحة. تنفيذ قائمة الانتظار ذات الأولوية، كود جافا:

PriorityQueue<Integer> numbers = new PriorityQueue<>();

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

طرق Java PriorityQueue

تحتوي فئة Java PriorityQueue على طرق مهمة لإضافة العناصر وإزالتها والتحقق منها.

إدراج عناصر في قائمة انتظار الأولوية

• تقوم الإضافة المنطقية (object) بإدراج العنصر المحدد في قائمة انتظار الأولوية. يعود صحيحا في حالة النجاح. إذا كانت قائمة الانتظار ممتلئة، فستطرح الطريقة استثناءً.
• يقوم العرض المنطقي (الكائن) بإدراج العنصر المحدد في قائمة انتظار الأولوية هذه. إذا كانت قائمة الانتظار ممتلئة، فسترجع الطريقة خطأ.

يمكنك استخدام كلتا عمليتي الإضافة، ولا توجد اختلافات في حالات الأغلبية. فيما يلي مثال بسيط لبدء وإضافة العناصر إلى قائمة انتظار الأولوية.

import java.util.PriorityQueue;
import java.util.Queue;
public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue1 = new PriorityQueue<>();
        for (int i = 5; i > 0; i--) {
            priorityQueue1.add(i);
        }
        System.out.println(priorityQueue1);
    priorityQueue1.offer(0);
        System.out.println(priorityQueue1);
    }
}

الإخراج هو:

[1, 2, 4, 5, 3]
[0, 2, 1, 5, 3, 4]

يبدو ترتيب العناصر غريبًا، سنشرحه لاحقًا.

استرداد وإزالة العناصر من قائمة الانتظار ذات الأولوية

• إزالة منطقية (كائن) تزيل مثيلًا واحدًا للعنصر المحدد من قائمة الانتظار هذه، إذا كان موجودًا.
• يقوم Object poll() باسترداد وإزالة رأس قائمة الانتظار هذه. إرجاع قيمة فارغة إذا كانت قائمة الانتظار فارغة.
• يزيل void Clear() كافة العناصر من قائمة انتظار الأولوية.
• يسترد Object element() رأس قائمة الانتظار هذه دون إزالته. يرمي NoSuchElementException إذا كانت قائمة الانتظار فارغة.
• يسترد Object peek() رأس قائمة الانتظار دون إزالته. إرجاع قيمة فارغة إذا كانت قائمة الانتظار فارغة.

import java.util.PriorityQueue;
import java.util.Queue;

public class Priority2 {
    public static void main(String[] args) {
        Queue<Integer> priorityQueue = new PriorityQueue<>();
        //put 5 elements to the queue using add
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of the queue = " + priorityQueue.peek());
        //removing element by element from the queue using poll and print it out
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
        //put 5 new elements into the empty queue using offer
        for (int i = 10; i > 5; i--) {
            priorityQueue.offer(i);
        }
        System.out.println("now the head of the queue = " + priorityQueue.peek());
        System.out.println("the queue before removing 9:");
        System.out.println(priorityQueue);
        priorityQueue.remove(9);
        System.out.println("the queue after removing 9:");
        System.out.println(priorityQueue);
        //removing all the elements from the queue
        priorityQueue.clear();
        System.out.println(priorityQueue);
        //trying to print out the head of the empty Queue using peek - we'll get null
        System.out.println(priorityQueue.peek());
        //trying to print out the head of the empty Queue using element - we'll get the exception
        System.out.println(priorityQueue.element());
    }
}

الإخراج:

the head of the queue = 1
1
2
3
4
5
now the head of the queue = 6
the queue before removing 9:
[6, 7, 9, 10, 8]
the queue after removing 9:
[6, 7, 8, 10]
[]
null
Exception in thread "main" java.util.NoSuchElementException
  at java.base/java.util.AbstractQueue.element(AbstractQueue.java:136)
  at Priority2.main(Priority2.java:32)

كما ترى، فإن محاولة طباعة رأس قائمة الانتظار الفارغة باستخدام طريقة element() تؤدي إلى NoSuchElementexception .

مقارنة قائمة الانتظار ذات الأولوية

• Comparator comparator() يُرجع المقارنة المستخدمة لترتيب العناصر في قائمة الانتظار. تُرجع قيمة فارغة إذا تم فرز قائمة الانتظار وفقًا للترتيب الطبيعي لعناصرها.

قائمة انتظار أولوية Java، مثال مع المقارنة

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

import java.util.PriorityQueue;
import java.util.Comparator;

class Priority3 {
    public static void main(String[] args) {
        // Creating a priority queue with myComparator
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new MyComparator());
        for (int i = 5; i > 0; i--) {
            priorityQueue.add(i);
        }
        System.out.println("the head of Queue = " + priorityQueue.peek());
        while (!priorityQueue.isEmpty()) {
            System.out.println(priorityQueue.poll());
        }
    }
}

class MyComparator implements Comparator<Integer> {
    @Override
    public int compare(Integer number1, Integer number2) {
        int value = number1.compareTo(number2);
        //sorting elements from maximal to minimal
        if (value > 0) {
            return -1;
        } else if (value < 0) {
            return 1;
        } else {
            return 0;
        }
    }
}

الإخراج:

the head of Queue = 5
5
4
3
2
1

رأس قائمة الانتظار الآن ليس الحد الأدنى، بل الحد الأقصى، وتم تغيير الترتيب إلى العكس.

التكرار عبر PriorityQueue باستخدام المكرر

يعد ProrityQueue جزءًا من إطار عمل المجموعة ويقوم بتنفيذ واجهة Iterable<> . للتكرار على عناصر قائمة انتظار الأولوية، يمكنك استخدام طريقة التكرار () . هنا مثال:

import java.util.PriorityQueue;
import java.util.Iterator;
import java.util.Queue;

class Priority4 {
   public static void main(String[] args) {
       // Creating a priority queue
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       //put 5 elements to the queue using add
       for (int i = 5; i > 0; i--) {
           priorityQueue.add(i);
       }
       //Iterating via iterator() method
       Iterator<Integer> iterator = priorityQueue.iterator();
       while (iterate.hasNext()) {
           System.out.print(iterator.next() + " ");
       }
   }
}

الإخراج:

1 2 4 5 3 

المزيد من أساليب قائمة الانتظار ذات الأولوية

• تحتوي القيمة المنطقية على (Object o) على إرجاع صحيح إذا كانت قائمة الانتظار تحتوي على العنصر o.
• int size() يُرجع عدد العناصر في قائمة الانتظار هذه.
• يقوم Object[] toArray() بإرجاع مصفوفة تحتوي على كافة العناصر الموجودة في قائمة الانتظار هذه.

هنا مثال:

import java.util.PriorityQueue;
import java.util.Queue;

public class Priority5 {
   public static void main(String[] args) {
       Queue<Integer> priorityQueue = new PriorityQueue<>();
       for (int i = 5; i > 0; i--) {
           priorityQueue.offer(i);
       }

       System.out.println("our queue: " + priorityQueue);

       System.out.println("Does our queue contain 8?  " + priorityQueue.contains(8));
       System.out.println("Does queue contain 5?  " + priorityQueue.contains(5));

       System.out.println("The quantity of queue elements: " + priorityQueue.size());
       Object[] myArray = priorityQueue.toArray();
       System.out.println("print out our array:");
       for (Object name : myArray) {
           System.out.println(name);
       }
   }
}

الإخراج:

our queue: [1, 2, 4, 5, 3]
Does our queue contain 8?  false
Does our queue contain 5?  true
The quantity of queue elements: 5
print out our array:
1
2
4
5
3

تعريف قائمة الأولوية جافا 8

إذا قمت بفتح وثائق Java 8 لقائمة انتظار الأولوية، فستجد هناك التعريف التالي: قائمة انتظار أولوية غير محدودة تعتمد على كومة الأولوية. يتم ترتيب عناصر قائمة الانتظار ذات الأولوية وفقًا لترتيبها الطبيعي، أو بواسطة مقارن يتم توفيره في وقت إنشاء قائمة الانتظار، اعتمادًا على المنشئ المستخدم. قائمة انتظار الأولوية لا تسمح بالعناصر الفارغة. قائمة الانتظار ذات الأولوية التي تعتمد على الترتيب الطبيعي لا تسمح أيضًا بإدراج كائنات غير قابلة للمقارنة (قد يؤدي القيام بذلك إلى ClassCastException). الكومة هي كلمة مهمة جدا هنا. ويشرح خصائص ترتيب عناصر قائمة الانتظار ذات الأولوية.

مبدأ عمل PriorityQueue: Binary Heap

لنبدأ بمثال. لنقم بإنشاء كائنين ينفذان واجهة قائمة الانتظار. واحد منهم LinkedList، والثاني — PriorityQueue. كلاهما لديه 5 عناصر من الأعداد الصحيحة (1،2،3،4 و 5) ونبدأ في وضع العناصر في قوائم الانتظار الخاصة بنا من الأكبر إلى الأصغر. إذن، الأول يأتي 5، ثم 4، 3، 2 والأخير سيكون 1. ثم اطبع كلا القائمتين للتحقق من الترتيب.

Queue<Integer> queueL = new LinkedList<>();
    for (int i = 5; i > 0; i--) {
        queueL.add(i);
    }
    System.out.println("LinkedList Queue (FIFO): " + queueL);
    Queue<Integer> priorityQueue = new PriorityQueue<>();

    for (int i = 5; i > 0; i--) {
    priorityQueue.offer(i);
    }
    System.out.println("PriorityQueue: " + priorityQueue)

نتيجة عمل هذه التعليمات البرمجية هي التالية:

LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue: [1, 2, 4, 5, 3]

حسنًا، ترتيب القائمة المرتبطة أمر يمكن التنبؤ به ومفهوم. يتم طلبه وفقًا لمبدأ FIFO. لقد بدأنا بالرقم 5، لذا فإن هذا العنصر هو الأول في السطر، ثم يأتي بالرقم 4 وهكذا. ماذا يمكننا أن نقول عن ترتيب قائمة الانتظار ذات الأولوية؟ قال Docs أن عناصر قائمة الانتظار ذات الأولوية يتم ترتيبها وفقًا لترتيبها الطبيعي، أو بواسطة مقارن يتم توفيره في وقت إنشاء قائمة الانتظار. ومع ذلك، لا يبدو أن هذا الترتيب "طبيعي" في معنى الفرز الخطي. نفضل أن نتوقع [1، 2، 3، 4، 5]، وليس [1، 2، 4، 5، 3]. لفهم سبب كون ترتيب الاسترداد على هذا النحو، يجب أن نتذكر قائمة انتظار الأولوية القائمة على الكومة. ما هي الكومة؟ إنها بنية بيانات تعتمد على الشجرة الثنائية . الخاصية الرئيسية للكومة: أولوية كل والد أكبر من أولويات أبنائه. اسمحوا لي أن أذكرك أن الشجرة تسمى ثنائية كاملة إذا لم يكن لدى كل من الوالدين أكثر من طفلين، وينتقل ملء المستويات من الأعلى إلى الأسفل (من نفس المستوى - من اليسار إلى اليمين). تعيد الكومة الثنائية تنظيم نفسها في كل مرة تتم فيها إضافة عناصر أو إزالتها منها. في حالة الكومة الصغيرة، يذهب أصغر عنصر إلى الجذر بغض النظر عن ترتيب إدراجه. قائمة انتظار الأولوية بناءً على هذه الكومة الصغيرة. وهذا يعني أنه في حالة عناصر قائمة الانتظار الرقمية، سيكون العنصر الأول في قائمة الانتظار هو الحد الأدنى من هذه الأرقام. إذا قمت بحذف الجذر، يصبح الأصغر التالي هو الجذر.

دعونا ننتقل إلى مثالنا.

الخطوة 1. نضع الرقم "5" في قائمة انتظار الأولوية. يصبح جذرًا. الخطوة 2. نضيف "4" إلى قائمة انتظار الأولوية. 4 <5، لذا يجب أن يكون العنصر الجديد أعلى من العنصر القديم. يصبح الرقم 4 جذرًا، والرقم 5 هو الابن الأيسر له. الآن أصبحت بنية البيانات في Java هي [4، 5] الخطوة 3. أضفنا "3". ويصير مؤقتا ابن حق لجذر (٤). ومع ذلك، 3 < 4، لذلك ينبغي علينا رفعه. تبادل 3 و 4. الآن لدينا هيكل مثل [3، 5، 4] الخطوة 4. نضيف "2". يصبح الطفل الأيسر من 5. 2<5، لذا استبدلهم. 2 يصبح الطفل الأيسر لـ 3، 2 < 3، لذلك عملية تبادل أخرى. الآن لدينا هيكل [2،3،4،5] الخطوة 5. نضيف "1". فهو يأتي من الابن الأيمن للرقم 3 إلى الابن الأيسر للرقم 2، ثم يذهب إلى الجذر. بنية البيانات الناتجة: [1,2,4,5,3] تبدأ عملية الإزالة من الجذر، وتؤدي إلى الإجراءات العكسية. لذلك، لدينا أولاً 1 كجذر، ثم 2، 3، 4 وأخيراً 5. ولهذا السبب يتم استخدام عملية إزالة الاستطلاع ()

while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }

لقد حصلنا على "مرتبة" في الإخراج الخطي:

1
2
3
4
5

لذلك يمكن أن تكون قائمة الانتظار ذات الأولوية فعالة لبعض العمليات. يستغرق الأمر O(log N) وقتًا لإدراج كل عنصر وحذفه، ويمكنك الحصول على الحد الأدنى من العناصر في O(1). هنا هو المثال الكامل:

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
   public static void main(String[] args) {

       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();

       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }

       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval):
1
2
3
4
5

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

ما يجب أن تعرفه عن قائمة الانتظار ذات الأولوية قائمة مختصرة

• قائمة الانتظار ذات الأولوية لا تسمح بالكائنات الفارغة.
• يمكنك إضافة كائنات قابلة للمقارنة فقط إلى PriorityQueue.
• تم إنشاء قائمة انتظار الأولوية على شكل كومة دقيقة، وهي نوع من الشجرة الثنائية. العنصر الأدنى هو الجذر. يتم ترتيب كائنات قائمة انتظار الأولوية بشكل افتراضي بالترتيب الطبيعي.
• يمكنك استخدام المقارنة إذا كنت بحاجة إلى ترتيب مخصص.
• PriorityQueue ليست آمنة لمؤشر الترابط، لذا من الأفضل استخدام PriorityBlockingQueue للعمل في بيئة متزامنة.
• توفر PriorityQueue وقتًا O(log(n)) لطرق الإضافة والاستقصاء وO(1) للحصول على الحد الأدنى من العناصر.