Java Priority Queue: לא תור קלאסי

במאמר זה נלמד תור עדיפות, מחלקת Java, המיישמת ממשק Queue. מה מתכנת יודע על ממשק תור רגיל? קודם כל, הממשק הזה מבוסס על עקרון ה-FIFO או "ראשון יוצא ראשון". זה מזכיר תור רגיל במשמעותו המשותפת. אתה רוצה לקבל קפה ממקדרייב? אם המכונית שלך היא הראשונה ליד החלון, תקבל את הקפה שלך לפני הנהג הבא.

הצהרת ממשק תור

public interface Queue<E> extends Collection<E>

מהו תור עדיפות

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

בוני מחלקות והצהרה של PriorityQueue

מחלקה PriorityQueue מספקת 6 דרכים שונות לבנות תור עדיפות ב-Java.

• PriorityQueue() - תור ריק עם קיבולת ההתחלתית המוגדרת כברירת מחדל (11) שמסדרת את האלמנטים שלו לפי הסדר הטבעי שלהם.
• PriorityQueue(Collection c) - תור ריק המכיל את האלמנטים באוסף שצוין.
• PriorityQueue(int initialCapacity) - תור ריק עם הקיבולת הראשונית שצוינה שמסדר את האלמנטים שלו לפי הסדר הטבעי שלהם.
• PriorityQueue(int initialCapacity, Comparator comparator) - תור ריק עם הקיבולת הראשונית שצוינה שמסדר את האלמנטים שלו לפי המשווה שצוין.
• PriorityQueue(PriorityQueue c) - תור ריק המכיל את האלמנטים בתור העדיפות שצוין.
• PriorityQueue(SortedSet c) - תור ריק המכיל את האלמנטים בסט הממוין שצוין.

תור עדיפות ב-Java מוכרז בדרך הבאה:

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

יצירת PriorityQueue

בואו ניצור תור עדיפות של מספרים שלמים. יישום תור עדיפות, קוד Java:

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

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

שיטות Java PriorityQueue

למחלקת PriorityQueue Java יש שיטות חשובות להוסיף, להסיר ולבדוק אלמנטים.

הכנס אלמנטים לתור עדיפות

• boolean add(object) מכניס את האלמנט שצוין לתור העדיפות. מחזיר נכון במקרה של הצלחה. אם התור מלא, השיטה זורקת חריגה.
• boolean offer(object) מכניס את האלמנט שצוין לתור העדיפות הזה. אם התור מלא, השיטה מחזירה false.

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

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]

סדר האלמנטים נראה מוזר, נסביר זאת בהמשך.

אחזור והסרה של אלמנטים מהתור העדיפות

• boolean remove(object) מסיר מופע בודד של הרכיב שצוין מהתור הזה, אם הוא קיים.
• Object poll() מאחזר ומסיר את ראש התור הזה. מחזירה null אם התור ריק.
• void clear() מסיר את כל האלמנטים מתור העדיפות.
• Object element() מאחזר את ראש התור הזה מבלי להסיר אותו. זורק NoSuchElementException אם התור ריק.
• Object peek() מאחזר את ראש התור מבלי להסיר אותו. מחזירה null אם התור ריק.

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() מחזיר את המשווה ששימש לסדר את האלמנטים בתור. מחזירה null אם התור ממוין לפי הסדר הטבעי של האלמנטים שלו.

תור העדיפות של Java, דוגמה עם השוואת

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

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 הוא חלק ממסגרת Collection ומיישם את הממשק Iterable<> . כדי לחזור על אלמנטים של תור עדיפות אתה יכול להשתמש בשיטת iterator() . הנה דוגמא:

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 

שיטות נוספות של PriorityQueue

• boolean contains(Object o) מחזירה true אם התור מכיל את האלמנט 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

הגדרת PriorityQueue Java 8

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

העיקרון של עבודת PriorityQueue: ערימה בינארית

נתחיל עם דוגמה. בואו ניצור שני אובייקטים המיישמים את ממשק ה-Queue. אחד מהם 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]

ובכן, סדר ה-linkedlist הוא צפוי ומובן. הוא מסודר על פי עקרון FIFO. התחלנו עם 5, אז האלמנט הזה הוא הראשון בתור, ואז עובר 4 וכן הלאה. מה אנחנו יכולים לספר על הזמנת תור עדיפות? Docs אמרו שהרכיבים של תור העדיפות מסודרים לפי הסדר הטבעי שלהם, או על ידי Comparator המסופק בזמן בניית התור. אולם נראה שסדר זה אינו "טבעי" במשמעות המיון ליניארית. אנחנו מעדיפים לצפות ל-[1, 2, 3, 4, 5], לא [1, 2, 4, 5, 3]. כדי להבין מדוע סדר האחזור הוא כמו שהוא, עלינו לזכור את תור העדיפות המבוסס על ערימה. מהי הערימה? זהו מבנה נתונים המבוסס על עץ בינארי . תכונתה העיקרית של הערימה: העדיפות של כל הורה גדולה יותר מסדר העדיפויות של ילדיו. הרשו לי להזכיר לכם שעץ נקרא בינארי שלם אם לכל הורה אין יותר משני ילדים, ומילוי הרמות עובר מלמעלה למטה (מאותה רמה - משמאל לימין). ערימה בינארית מארגנת את עצמה מחדש בכל פעם שאלמנטים מתווספים או מסירים ממנו. במקרה של ערימה קטנה, האלמנט הקטן ביותר הולך לשורש ללא קשר לסדר ההחדרה שלו. תור עדיפות המבוסס על ערימה מינימלית זו. כלומר, במקרה של רכיבי תור מספרים, האלמנט הראשון של התור יהיה המינימלי מבין המספרים הללו. אם תמחק את השורש, הקטן הבא יהפוך לשורש.

בואו נפנה לדוגמא שלנו.

שלב 1. הכנסנו '5' לתור העדיפות. זה הופך לשורש. שלב 2. אנו מוסיפים '4' לתור העדיפות. 4 <5, אז האלמנט החדש צריך להיות גבוה יותר מהישן יותר. ה-4 הופך לשורש, 5 הוא הילד השמאלי שלו. כעת מבנה הנתונים בג'אווה הוא [4, 5] שלב 3. אנו מוסיפים '3'. באופן זמני הוא הופך להיות בן שורש נכון (4). עם זאת, 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. זו הסיבה לשימוש בהסרת הפעולה poll()

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

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

מה שאתה צריך לדעת על תור עדיפות. רשימה קצרה

• Priority Queue אינו מאפשר אובייקטי NULL.
• אתה יכול להוסיף רק אובייקטים דומים לתוך PriorityQueue.
• תור עדיפות בנוי כ-Mine Heap, מעין עץ בינארי. האלמנט המינימלי הוא שורש. האובייקטים של תור העדיפות מסודרים כברירת מחדל בסדר טבעי.
• אתה יכול להשתמש ב-Comparator אם אתה צריך הזמנה מותאמת אישית.
• PriorityQueue אינו בטוח בשרשור, אז כדאי להשתמש ב-PriorityBlockingQueue כדי לעבוד בסביבה במקביל.
• PriorityQueue מספק זמן O(log(n)) עבור שיטות הוספה וסקר ו-O(1) כדי לקבל אלמנטים מינימליים.