Java Priority Queue: nem klasszikus várólista

Ebben a cikkben egy prioritási sort, a Java osztályt ismerjük meg, amely a Queue felületet valósítja meg. Mit tud egy programozó a normál sorinterfészről? Először is, ez az interfész a FIFO elven vagy az „első az elsőben” elven alapul. Ez egy rendes sorra emlékeztet a szokásos jelentésében. Szeretnél kávét kapni a McDrive-tól? Ha az Ön autója az első az ablak mellett, akkor a következő sofőr előtt kapja meg a kávéját.

Queue Interface deklaráció

public interface Queue<E> extends Collection<E>

Mi az a prioritási sor

Mi az a prioritási sor? Mindenekelőtt egy olyan osztályról van szó, amely megvalósítja a Queue interfészt abban az esetben, ha egy elemet hátulról illeszt be, és elemet távolít el a fejből. Ez azonban nem egy szokásos sor belülről. A Java prioritási sorelemek sorrendje az elemek prioritásától függ. A legmagasabb prioritású elem átkerül a sor fejébe. Ha törli (kiszolgálja) a legmagasabb rangú elemet, a második a fejhez megy, hogy megkapja a kávéját. Hogyan határozzák meg a prioritást? A dokumentáció szerint az elsőbbségi sor elemeit természetes sorrendjük szerint, vagy a sorépítéskor biztosított Összehasonlító segítségével rendezzük, attól függően, hogy melyik konstruktort használják. Prioritási sor egy prioritási min halom alapján. Ez azt jelenti, hogy számsorelemek esetén a sor első eleme ezeknek a számoknak a minimuma lesz. A definíció elolvasása után az újonc diákok gyakran azt gondolják, hogy a prioritási sor lineárisan van rendezve. Azaz, ha mondjuk olyan sort használunk, amelynek elemei természetes számok, akkor az első elem lesz a legkisebb, az utolsó pedig a legnagyobb. Ez nem teljesen igaz. Ahhoz, hogy megértse, hogyan működik valójában a prioritási sor, és mit ad, ki kell találnia a kupac működését. A prioritási sor belső szerkezetét egy kicsit későbbi példán keresztül tekintjük át. Most térjünk ki a külső tulajdonságaira. akkor az első elem lesz a legkisebb, és az utolsó - a legnagyobb. Ez nem teljesen igaz. Ahhoz, hogy megértse, hogyan működik valójában a prioritási sor, és mit ad, ki kell találnia a kupac működését. A prioritási sor belső szerkezetét egy kicsit későbbi példán keresztül tekintjük át. Most térjünk ki a külső tulajdonságaira. akkor az első elem lesz a legkisebb, és az utolsó - a legnagyobb. Ez nem teljesen igaz. Ahhoz, hogy megértse, hogyan működik valójában a prioritási sor, és mit ad, ki kell találnia a kupac működését. A prioritási sor belső szerkezetét egy kicsit későbbi példán keresztül tekintjük át. Most térjünk ki a külső tulajdonságaira.

PriorityQueue osztálykonstruktorok és deklaráció

A PriorityQueue osztály 6 különböző módot biztosít prioritási sor létrehozására Java nyelven.

• PriorityQueue() - üres sor az alapértelmezett kezdeti kapacitással (11), amely elemeit természetes sorrendjük szerint rendezi.
• PriorityQueue(Collection c) - üres sor, amely a megadott gyűjtemény elemeit tartalmazza.
• PriorityQueue(int kezdeti kapacitás) - üres sor a megadott kezdeti kapacitással, amely elemeit természetes sorrendjük szerint rendezi.
• PriorityQueue(int kezdeti kapacitás, összehasonlító összehasonlító) - üres sor a megadott kezdeti kapacitással, amely az elemeit a megadott összehasonlító szerint rendezi.
• PriorityQueue(PriorityQueue c) - üres sor, amely a megadott prioritási sor elemeit tartalmazza.
• PriorityQueue(SortedSet c) - üres sor, amely a megadott rendezett halmaz elemeit tartalmazza.

A Java prioritási sor a következő módon deklarálva:

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

PriorityQueue létrehozása

Hozzunk létre egy prioritási sort egész számokból. Priority Queue implementáció, Java kód:

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

Létrehoztunk egy prioritási sort, argumentumok nélkül. Ebben az esetben a prioritási sor feje a sor minimális száma. Ha eltávolítja a fejet, a következő legkisebb elem fogja ezt a helyet. Így az elemeket növekvő sorrendben távolíthatja el a sorból. Szükség esetén a Comparator felületen módosíthatja a rendelés elvét.

Java PriorityQueue Methods

A PriorityQueue Java osztály fontos módszereket tartalmaz az elemek hozzáadására, eltávolítására és ellenőrzésére.

Szúrjon be elemeket a prioritási sorba

• A logikai add(object) beszúrja a megadott elemet a prioritási sorba. Siker esetén igazat ad vissza. Ha a sor megtelt, a metódus kivételt dob.
• A logikai ajánlat(object) beszúrja a megadott elemet ebbe a prioritási sorba. Ha a sor megtelt, a metódus false értéket ad vissza.

Mindkét összeadási műveletet használhatja, a legtöbb esetben nincs különbség. Íme egy kis példa a kezdeményezésre és az elemek prioritási sorba való hozzáadására.

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);
    }
}

A kimenet a következő:

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

Az elemek sorrendje furcsának tűnik, ezt később elmagyarázzuk.

Elemek lekérése és eltávolítása a prioritási sorból

• A boolean remove(object) eltávolítja a megadott elem egyetlen példányát a sorból, ha az jelen van.
• Az Object poll() lekéri és eltávolítja ennek a sornak a fejét. Null értékkel tér vissza, ha a sor üres.
• A void clear() eltávolítja az összes elemet a prioritási sorból.
• Az Object element() lekéri ennek a sornak a fejét anélkül, hogy eltávolítaná. A NoSuchElementException parancsot dobja , ha a sor üres.
• Az Object peek() lekéri a sor fejét anélkül, hogy eltávolítaná azt. Null értékkel tér vissza, ha a sor üres.

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());
    }
}

A kimenet:

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)

Amint láthatja, az üres Queue fejlécének kinyomtatása az element() metódussal NoSuchElementexception- hez vezet .

PriorityQueue Comparator

• Comparator A comparator() azt a komparátort adja vissza, amely a sorban lévő elemek sorrendjét használta. Null értékkel tér vissza, ha a sor elemeinek természetes sorrendje szerint van rendezve.

Java prioritási sor, példa összehasonlítóval

A fenti kódpéldákban természetes (növekvő) sorrendet használtunk, de néha meg kell változtatni. Itt van példa a Java prioritási sorra, ahol létrehozzuk a saját belső összehasonlító osztályunkat, amely megvalósítja a Comparator felületet. Összehasonlítónk a legnagyobbtól a legkisebbig rendezi az elemeket.

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;
        }
    }
}

A kimenet:

the head of Queue = 5
5
4
3
2
1

A Queue fejléce most nem a minimális, hanem a maximális elem, és a sorrend fordítottra változott.

Iteráció a PriorityQueue felett az iterátor segítségével

A ProrityQueue a Collection keretrendszer része, és megvalósítja az Iterable<> felületet. A prioritási sor elemei feletti iterációhoz használhatja az iterator() metódust. Íme egy példa:

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() + " ");
       }
   }
}

A kimenet:

1 2 4 5 3 

További PriorityQueue metódusok

• A boolean include(Object o) értéke igaz, ha a sor tartalmazza az o elemet.
• Az int size() a sorban lévő elemek számát adja vissza.
• Az Object[] toArray() egy tömböt ad vissza, amely a sor összes elemét tartalmazza.

Íme egy példa:

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);
       }
   }
}

A kimenet:

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 definíció

Ha megnyitja a priorityqueue java 8 dokumentációját, ott a következő definíciót találja: Korlátlan prioritású sor prioritáshalmon alapuló. A prioritási sor elemei a természetes sorrendjük szerint, vagy a sorépítéskor biztosított Összehasonlító segítségével kerülnek rendezésre, attól függően, hogy melyik konstruktort használják. A prioritási sor nem engedélyez null elemeket. A természetes sorrendre támaszkodó prioritási sor szintén nem teszi lehetővé nem összehasonlítható objektumok beszúrását (ez ClassCastException kivételt eredményezhet). A kupac itt nagyon fontos szó. Elmagyarázza a Priority Queue elemek sorrendjének tulajdonságait.

A PriorityQueue munka elve: Binary Heap

Kezdjük egy példával. Hozzon létre két objektumot, amelyek megvalósítják a Queue felületet. Az egyik LinkedList, a második a PriorityQueue. Mindkettőben 5 egész elem van (1,2,3,4 és 5), és elkezdjük az elemeket a legnagyobbtól a legkisebbig rakni a sorainkba. Tehát az első 5, majd 4, 3, 2 és az utolsó 1 lesz. Ezután nyomtassa ki mindkét listát a sorrend ellenőrzéséhez.

   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)

A kód működésének eredménye a következő:

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

Nos, a linkedlist sorrendje kiszámítható és érthető. Megrendelése FIFO elv szerint történik. 5-tel kezdtük, tehát ez az elem a legelső a sorban, aztán megy a 4-es és így tovább. Mit mondhatunk a prioritási sorrendről? A Docs azt mondta, hogy az elsőbbségi sor elemei a természetes sorrendjük szerint vannak rendezve, vagy a sorépítéskor biztosított Összehasonlító segítségével. Ez a sorrend azonban nem tűnik „természetesnek” a lineáris rendezés értelmében. Inkább azt várjuk, hogy [1, 2, 3, 4, 5], ne pedig [1, 2, 4, 5, 3]. Ahhoz, hogy megértsük, miért olyan a visszakeresés sorrendje, mint amilyen, fel kell idéznünk azt a halomra épülő prioritási sort. Mi az a kupac? Ez egy bináris fán alapuló adatstruktúra. A halom fő tulajdonsága: minden szülő prioritása nagyobb, mint a gyermekeié. Hadd emlékeztesselek arra, hogy egy fát teljes binárisnak nevezünk, ha minden szülőnek legfeljebb két gyermeke van, és a szintek kitöltése fentről lefelé halad (ugyanarról a szintről - balról jobbra). A bináris kupac minden egyes alkalommal újraszervezi magát, amikor elemeket ad hozzá vagy eltávolít belőle. Min-heap esetén a legkisebb elem kerül a gyökérbe, függetlenül a beillesztési sorrendtől. Elsőbbségi sor ezen a minimális kupon alapján. Ez azt jelenti, hogy számsorelemek esetén a sor első eleme ezek közül a számok minimuma lesz. Ha törli a gyökeret, a következő legkisebb gyökér lesz.

Térjünk rá példánkra.

1. lépés: '5'-öt teszünk a prioritási sorba. Gyökérré válik. 2. lépés: '4'-et adunk a prioritási sorhoz. 4 <5, tehát az új elem magasabb legyen, mint a régebbi. A 4-ből gyökér lesz, az 5-ből a bal gyermeke. Most a Java adatszerkezete [4, 5] 3. lépés. Hozzáadjuk a „3”-at. Átmenetileg a gyökér jobb gyermekévé válik (4). Viszont 3 < 4, ezért emeljük fel. Cserélje ki a 3-at és a 4-et. Most olyan struktúránk van, mint például [3, 5, 4] 4. lépés. Hozzáadjuk a '2'-t. 5. 2<5 bal gyermeke lesz, ezért cserélje ki őket. 2 a 3 bal gyermekévé válik, 2 < 3, tehát még egy cserefolyamat. Most megvan a struktúra [2,3,4,5] 5. lépés.Hozzáadjuk az „1”-et. A 3 jobb gyermekétől a 2 bal gyermekéig jön, majd a gyökérig megy. Az eredmény adatszerkezete: [1,2,4,5,3] Az Eltávolítási folyamat egy gyökérből indul ki, és fordított eljárásokat vált ki. Tehát először 1 van gyökérként, majd 2, 3, 4 és végül 5. Ezért használjuk a poll() eltávolítási műveletet.

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

„rendezve” van a lineáris értelmes kimenetben:

1
2
3
4
5

Így a prioritási sor hatékony lehet bizonyos műveleteknél. Az egyes elemek beszúrása és törlése O(log N) időbe telik, és az O(1)-ben megkaphatja a minimális elemet. Íme a teljes példa:

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

Fontos megérteni, hogy a prioritási sorok bináris kupacokon alapulnak, így nem lineárisan rendezik az elemeket. A gyökértől a levélig minden út rendezett, de a gyökértől eltérő utak nem. Ez azt jelenti, hogy nagyon gyorsan megkaphatja a sor minimális elemét.

Amit az elsőbbségi sorról tudni kell. Rövid lista

• A Priority Queue nem engedélyezi a NULL objektumokat.
• Csak összehasonlítható objektumokat adhat hozzá a PriorityQueue-hoz.
• A prioritási sor mini kupacként, egyfajta bináris faként épül fel. A minimális elem egy gyökér. A prioritási sor objektumai alapértelmezés szerint természetes sorrendben vannak rendezve.
• Használhatja az Összehasonlítót, ha egyedi rendelésre van szüksége.
• A PriorityQueue nem szálbiztos, ezért jobb, ha a PriorityBlockingQueue-t használja, ha párhuzamos környezetben szeretne dolgozni.
• A PriorityQueue O(log(n)) időt biztosít a hozzáadási és lekérdezési módszerekhez, és O(1) időt biztosít a minimális elemek beszerzéséhez.