תור עדיפויות ב-Java

מדי פעם אנו צריכים לעבד פריטים של תור בסדר מסוים. תור עדיפויות הוא מבנה נתונים שעושה את העבודה. תור עדיפויות ב-Java שונה מתור "רגיל". במקום "הראשון שנכנס, ראשון שיוצא", היא מפעילה את הפריטים לפי סדר העדיפות שלהם.

תור עדיפויות ב-Java

המחלקה java.util.PriorityQueue מספקת לנו יישום של סוג מידע כזה, באמצעות יישום של מבנה הנתונים "ערימת עדיפויות" בפנים. תור עדיפויות ב-Java הוא תור ללא הגבלה. הוא הובא ל-Java בגרסה 1.5 והוגדל בשחרור Java SE 8. תור עדיפויות מיושם בפנים באמצעות מבנה נתונים "ערימת עדיפויות". הנה ההיררכיה של מחלקת PriorityQueue: תרשים של מחלקת PriorityQueue:

בניית תור עדיפויות ב-Java

1. PriorityQueue() – יוצר תור עדיפויות עם קיבולת ראשית ברירת מחדל, כלומר 11
2. PriorityQueue(Collection c) – יוצר תור עדיפויות עם האיברים באוסף המצוין
3. תור עדיפויות (int initialCapacity) – יוצר תור עדיפויות עם הקיבולת ההתחלתית המצוינת
4. תור עדיפויות (int initialCapacity, Comparator comparator) – יוצר תור עדיפויות עם הקיבולת ההתחלתית המצוינת וסידור האלמנטים בהתאם לממיר המצוין
5. תור עדיפויות (PriorityQueue c) – יוצר תור עדיפויות המכיל את האלמנטים בתוך תור העדיפויות המצוין
6. תור עדיפויות (SortedSet c) – יוצר תור עדיפויות המכיל את האלמנטים בתוך הסט הממויין המצוין

אלמנטי תור העדיפויות מסודרים לפי הסדר הטבעי שלהם אלא אם ורק אם אנו מספקים Comparator במהלך יצירתו. האלמנטים מסודרים בסדר עולה כברירת מחדל, ולכן ראש התור הוא האלמנט שעדיפותו הנמוכה ביותר. אם ישנם שני אלמנטים שזכאים להיות ראש התור באותו הזמן, סוג זה של קשרים נקרעים באופן שרירותי.

דוגמה על תור עדיפויות ב-Java

בואו ניצור PriorityQueue, המכיל מגוון משימות:

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

יצירת תור עדיפויות של משימות, המסודרות לפי הסדר הטבעי של String. בואו ניצור עוד תור עדיפויות שמסדר את המשימות בסדר הפוך לסדר הטבעי. לכן עלינו להעביר ממיר:

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

שיטות PriorityQueue ב-Java

כעת, בואו נצפה על כל השיטות הזמינות ל-PriorityQueue ונשתמש בהן:

1. Boolean add(E e) – שיטה זו מכניסה את האיבר הספציפי לתוך התור. כבר הוספנו 5 משימות לתור שלנו באמצעות שיטה זו.

2. Comparator comparator() – שיטה זו מחזירה את ה-Comparator המשמש לסידור האיברים בתוך התור הזה. היא מחזירה null אם לא הוגדר Comparator והתור מסודר על פי הסדר הטבעי של האיברים בו. לכן, אם נבצע:

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

   הפלט יהיה:

   null
   java.util.Collections$ReverseComparator@15db9742
   

3. בוליאני contains(Object o) – מחזיר true אם התור מכיל את האלמנט המצויין. בואו נבדוק האם "task3" שייך לתור העדיפות:

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

   זה מדפיס:

   true
   

4. בוליאני offer(E e) – בדיוק כמו בשיטת add(), שיטה זו גם מוסיפה אלמנט לתור. שיטות offer() ו-add() שונות קצת בתורים שמוגבלים לכמות, אך במקרה של PriorityQueue, שתי השיטות זהות. בניגוד ל-add(), offer() אינה זורקת חריגה גם אם הוא נכשל להוסיף את האלמנט לתור.

5. E peek() – מחזיר את ראש התור, או מחזיר null אם התור ריק. כלומר, היא מחזירה את האלמנט עם העדיפות הגבוהה ביותר. אז הקוד הבא:

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

   נותן לנו:

   task1
   task5
   

6. E poll() – שיטה זו מחזירה גם הראש של התור (אלמנט עם העדיפות הגבוהה ביותר), או מחזירה את הערך null אם התור ריק. אך בניגוד ל־peek(), היא גם מסירה את האלמנט. לכן, אם נקרא ל־poll():

   System.out.println(“Poll on tasks: ”+tasks.poll());
   System.out.println(“Poll on reverseTasks: ”+reverseTasks.poll());
   

   ואז peek:

   System.out.println(“Peek on tasks: ”+tasks.peek());
   System.out.println(“Peek on reverseTasks: ”+reverseTasks.peek());
   

   יהיה לנו את הפלט הבא:

   Poll on tasks: task1
   Poll on reverseTasks: task5
   Peek on tasks: task2
   Peek on reverseTasks: task4
   

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 Time Complexity

1. עבור שיטות ההכנסה וההוצאה, רמת זמן הריצה היא O(log(n))
2. עבור השיטות remove(Object) ו-contains(Object), רמת זמן הריצה היא לינארית
3. עבור שיטות החיפוש, יש לו רמת זמן ריצה קבועה

המימוש של תור עדיפויות זה אינו מסונכרן לפעולות בטרד, לכן, אם אנו זקוקים לגישה מסונכרנת, עלינו להשתמש ב-PriorityBlockingQueue. הפניה: מסמך ה- API