Java Priority Queue: hindi isang klasikong pila

Sa artikulong ito natutunan namin ang isang priyoridad na pila, ang klase ng Java, na nagpapatupad ng interface ng Queue. Ano ang alam ng isang programmer sa regular na Interface ng Queue? Una sa lahat, ang interface na ito ay batay sa prinsipyo ng FIFO o "first in first out". Na nagpapaalala sa isang regular na pila sa karaniwang kahulugan nito. Gusto mo bang makakuha ng kape mula sa McDrive? Kung ang iyong sasakyan ang mauna malapit sa bintana, kukunin mo ang iyong kape bago ang driver na susunod.

Pagpapahayag ng Interface ng Queue

public interface Queue<E> extends Collection<E>

Ano ang Priority Queue

Ano ang Priority Queue? Una sa lahat ito ay isang klase na nagpapatupad ng interface ng Queue sa kaso ng pagpasok ng isang elemento mula sa likod at pag-alis ng isang elemento mula sa ulo. Gayunpaman, hindi ito isang karaniwang pila sa loob. Ang pagkakasunud-sunod ng mga elemento ng priyoridad ng Java ay nakasalalay sa priyoridad ng mga elemento. Ang elementong may pinakamataas na priyoridad ay ililipat sa ulo ng pila. Kung tatanggalin mo (ihain) ang pinakamataas na ranggo na elemento, ang pangalawa ay pupunta sa ulo upang kunin ang kape nito. Paano tinutukoy ang priyoridad? Ayon sa dokumentasyon, ang mga elemento ng priyoridad na pila ay inayos ayon sa kanilang natural na pagkakasunud-sunod, o ng isang Comparator na ibinigay sa oras ng pagtatayo ng pila, depende sa kung aling constructor ang ginagamit. Isang priority queue batay sa isang priority min heap. Ibig sabihin, sa kaso ng mga elemento ng numero ng pila, ang unang elemento ng pila ay ang pinakamaliit sa mga numerong ito. Madalas pagkatapos basahin ang kahulugang ito, nagsisimulang isipin ng mga rookie na estudyante na ang priority queue ay pinagsunod-sunod sa isang linear na kahulugan. Iyon ay, kung, sabihin nating, gumagamit kami ng isang pila na ang mga elemento ay natural na mga numero, kung gayon ang unang elemento ay ang pinakamaliit, at ang huli - ang pinakamalaki. Ito ay hindi ganap na totoo. Upang maunawaan kung paano gumagana ang priority queue at kung ano ang ibinibigay nito, kailangan mong malaman kung paano gumagana ang heap. Isinasaalang-alang namin ang panloob na istraktura ng priority queue gamit ang isang halimbawa sa ibang pagkakataon. Ngayon ay pag-isipan natin ang mga panlabas na katangian nito. pagkatapos ay ang unang elemento ay ang pinakamaliit, at ang huli - ang pinakamalaking. Ito ay hindi ganap na totoo. Upang maunawaan kung paano gumagana ang priority queue at kung ano ang ibinibigay nito, kailangan mong malaman kung paano gumagana ang heap. Isinasaalang-alang namin ang panloob na istraktura ng priority queue gamit ang isang halimbawa sa ibang pagkakataon. Ngayon ay pag-isipan natin ang mga panlabas na katangian nito. pagkatapos ay ang unang elemento ay ang pinakamaliit, at ang huli - ang pinakamalaking. Ito ay hindi ganap na totoo. Upang maunawaan kung paano gumagana ang priority queue at kung ano ang ibinibigay nito, kailangan mong malaman kung paano gumagana ang heap. Isinasaalang-alang namin ang panloob na istraktura ng priority queue gamit ang isang halimbawa sa ibang pagkakataon. Ngayon ay pag-isipan natin ang mga panlabas na katangian nito.

PriorityQueue class constructors at deklarasyon

Ang klase ng PriorityQueue ay nagbibigay ng 6 na magkakaibang paraan upang makabuo ng priority queue sa Java.

• PriorityQueue() - walang laman na pila na may default na paunang kapasidad (11) na nag-order ng mga elemento nito ayon sa kanilang natural na pagkakasunud-sunod.
• PriorityQueue(Collection c) - walang laman na queue na naglalaman ng mga elemento sa tinukoy na koleksyon.
• PriorityQueue(int initialCapacity) - walang laman na pila na may tinukoy na paunang kapasidad na nag-order ng mga elemento nito ayon sa kanilang natural na pagkakasunud-sunod.
• PriorityQueue(int initialCapacity, Comparator comparator) - walang laman na pila na may tinukoy na paunang kapasidad na nag-order ng mga elemento nito ayon sa tinukoy na comparator.
• PriorityQueue(PriorityQueue c) - walang laman na pila na naglalaman ng mga elemento sa tinukoy na priority queue.
• PriorityQueue(SortedSet c) - walang laman na pila na naglalaman ng mga elemento sa tinukoy na pinagsunod-sunod na hanay.

Ang Priority Queue sa Java ay idineklara sa susunod na paraan:

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

Paggawa ng PriorityQueue

Gumawa tayo ng priority queue ng mga integer. Pagpapatupad ng Priority Queue, Java code:

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

Gumawa kami ng priority queue na walang argumento. Sa kasong ito, ang pinuno ng priyoridad na pila ay ang pinakamababang bilang ng pila. Kung aalisin mo ang ulo, ang susunod na pinakamaliit na elemento ang kukuha sa lugar na ito. Kaya maaari mong alisin ang mga elemento mula sa pila sa pataas na pagkakasunud-sunod. Kung kinakailangan maaari mong baguhin ang prinsipyo ng pag-order gamit ang interface ng Comparator.

Mga Paraan ng PriorityQueue ng Java

Ang PriorityQueue Java class ay may mahahalagang pamamaraan para magdagdag, mag-alis at magsuri ng mga elemento.

Ipasok ang Mga Elemento sa Priority Queue

• Ang boolean add(object) ay naglalagay ng tinukoy na elemento sa priority queue. Nagbabalik ng totoo kung sakaling magtagumpay. Kung ang pila ay puno, ang pamamaraan ay naghagis ng isang pagbubukod.
• Inilalagay ng boolean offer(object) ang tinukoy na elemento sa priority queue na ito. Kung ang pila ay puno, ang pamamaraan ay nagbabalik ng mali.

Maaari mong gamitin ang parehong mga pagpapatakbo ng pagdaragdag, walang mga pagkakaiba para sa karamihan ng mga kaso. Narito ang isang maliit na halimbawa ng pagsisimula at pagdaragdag ng mga elemento sa priority queue.

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

Ang output ay:

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

Ang pagkakasunud-sunod ng mga elemento ay tila kakaiba, ipapaliwanag namin ito mamaya.

Kinukuha at inaalis ang mga elemento mula sa Priority Queue

• Ang boolean remove(object) ay nag-aalis ng isang instance ng tinukoy na elemento mula sa queue na ito, kung ito ay naroroon.
• Kinukuha at inaalis ng Object poll() ang ulo ng pila na ito. Nagbabalik ng null kung walang laman ang pila.
• inaalis ng void clear() ang lahat ng elemento mula sa priority queue.
• Kinukuha ng Object element() ang head ng queue na ito nang hindi ito inaalis. Itinapon ang NoSuchElementException kung walang laman ang pila.
• Kinukuha ng Object peek() ang ulo ng pila nang hindi ito inaalis. Nagbabalik ng null kung walang laman ang pila.

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

Ang output:

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)

Tulad ng makikita mo, ang pagsisikap na i-print ang ulo ng walang laman na Queue gamit ang element() na pamamaraan ay humahantong sa NoSuchElementexception .

PriorityQueue Comparator

• Ibinabalik ng Comparator comparator() ang comparator na ginamit upang mag-order ng mga elemento sa queue. Ibinabalik ang null kung ang pila ay pinagsunod-sunod ayon sa natural na pagkakasunud-sunod ng mga elemento nito.

Java priority queue, halimbawa sa comparator

Gumamit kami ng natural (pataas) na pagkakasunud-sunod sa mga halimbawa ng code sa itaas, ngunit minsan dapat namin itong baguhin. Narito ang halimbawa ng Java priority queue, kung saan gumagawa kami ng sarili naming internal comparator class na nagpapatupad ng Comparator interface. Ang aming comparator ay mag-uuri ng mga elemento mula sa pinakamalaki hanggang sa pinakamaliit.

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

Ang Output:

the head of Queue = 5
5
4
3
2
1

Ang pinuno ng Queue ngayon ay hindi ang pinakamaliit, ngunit pinakamalaki na elemento, at ang pagkakasunud-sunod ay binago sa baligtad.

Pag-ulit sa PriorityQueue gamit ang iterator

Ang ProrityQueue ay isang bahagi ng balangkas ng Collection at ipinapatupad ang Iterable<> interface. Upang umulit sa mga elemento ng isang priority queue maaari mong gamitin ang iterator() method. Narito ang isang halimbawa:

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

Ang output:

1 2 4 5 3 

Higit pang mga paraan ng PriorityQueue

• Ang boolean contains(Object o) ay nagbabalik ng true kung ang queue ay naglalaman ng o element.
• int size() ay nagbabalik ng bilang ng mga elemento sa queue na ito.
• Ang Object[] toArray() ay nagbabalik ng array na naglalaman ng lahat ng elemento sa queue na ito.

Narito ang isang halimbawa:

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

Ang output:

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 kahulugan

Kung bubuksan mo ang dokumentasyong priorityqueue java 8, makikita mo doon ang susunod na kahulugan: Isang walang hangganang priyoridad na pila batay sa isang priority heap. Ang mga elemento ng priyoridad na pila ay inayos ayon sa kanilang natural na pagkakasunud-sunod, o ng isang Comparator na ibinigay sa oras ng pagbuo ng pila, depende kung aling constructor ang ginagamit. Ang isang priority queue ay hindi nagpapahintulot ng mga null na elemento. Ang isang priyoridad na pila na umaasa sa natural na pag-order ay hindi rin pinapayagan ang pagpasok ng mga hindi maihahambing na bagay (ang paggawa nito ay maaaring magresulta sa ClassCastException). Ang heap ay isang napakahalagang salita dito. Ipinapaliwanag nito ang mga katangian ng pag-order ng mga elemento ng Priority Queue.

Ang prinsipyo ng gawaing PriorityQueue: Binary Heap

Magsimula tayo sa isang halimbawa. Gumawa tayo ng dalawang bagay na nagpapatupad ng interface ng Queue. Isa sa kanila ang LinkedList, ang pangalawa — PriorityQueue. Pareho silang mayroong 5 elemento ng Integer (1,2,3,4 at 5) at sinimulan naming ilagay ang mga elemento sa aming mga pila mula sa pinakamalaki hanggang sa pinakamaliit. Kaya, ang una ay 5, pagkatapos ay 4, 3, 2 at ang huli ay magiging 1. Pagkatapos ay i-print ang parehong mga listahan upang suriin ang pagkakasunud-sunod.

   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)

Ang resulta ng gumaganang code na ito ay ang susunod:

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

Well, ang pagkakasunud-sunod ng linkedlist ay predictable at naiintindihan. Ito ay iniutos ayon sa prinsipyo ng FIFO. Nagsimula kami sa 5, kaya ang elementong ito ang pinakauna sa linya, pagkatapos ay napupunta sa 4 at iba pa. Ano ang masasabi natin tungkol sa priority queue order? Sinabi ng Docs na ang mga elemento ng priyoridad na pila ay inayos ayon sa kanilang natural na pagkakasunud-sunod, o ng isang Comparator na ibinigay sa oras ng paggawa ng pila. Gayunpaman, ang pagkakasunud-sunod na ito ay tila hindi "natural" sa linear na kahulugan ng pag-uuri. Mas gugustuhin naming asahan [1, 2, 3, 4, 5], hindi [1, 2, 4, 5, 3]. Upang maunawaan kung bakit ganito ang pagkakasunud-sunod ng pagkuha, dapat nating alalahanin ang priyoridad na pila batay sa isang tambak. Ano ang tambak? Ito ay isang istraktura ng data batay sa binary tree. Ang pangunahing pag-aari ng tambak: ang priyoridad ng bawat magulang ay mas malaki kaysa sa mga priyoridad ng mga anak nito. Ipaalala ko sa iyo na ang isang puno ay tinatawag na isang kumpletong binary kung ang bawat magulang ay may hindi hihigit sa dalawang anak, at ang pagpuno ng mga antas ay napupunta mula sa itaas hanggang sa ibaba (mula sa parehong antas - mula kaliwa hanggang kanan). Inaayos muli ng binary heap ang sarili nito sa tuwing idinaragdag o aalisin ang mga elemento dito. Sa kaso ng min-heap, ang pinakamaliit na elemento ay napupunta sa ugat anuman ang pagkakasunud-sunod ng pagpasok nito. Priyoridad na pila batay sa min-heap na ito. Ibig sabihin, sa kaso ng mga elemento ng numero ng pila, ang unang elemento ng pila ay ang pinakamaliit sa mga numerong ito. Kung tatanggalin mo ang ugat, ang susunod na pinakamaliit ay magiging ugat.

Bumaling tayo sa ating halimbawa.

Hakbang 1. Inilalagay namin ang '5' sa priority queue. Ito ay nagiging ugat. Hakbang 2. Idinaragdag namin ang '4' sa priority queue. 4 <5, kaya ang bagong elemento ay dapat na mas mataas kaysa sa mas luma. Ang 4 ay nagiging ugat, 5 ang kaliwang anak nito. Ngayon ang istraktura ng data sa Java ay [4, 5] Hakbang 3. Nagdagdag kami ng '3'. Pansamantala itong nagiging tamang anak ng ugat (4). Gayunpaman, 3 < 4, kaya dapat nating itaas ito. Palitan 3 at 4. Ngayon ay mayroon na tayong istraktura tulad ng [3, 5, 4] Hakbang 4. Nagdaragdag tayo ng '2'. Ito ay nagiging isang kaliwang anak ng 5. 2<5, kaya palitan sila. Ang 2 ay nagiging kaliwang anak ng 3, 2 < 3, kaya isa pang proseso ng palitan. Ngayon ay mayroon na tayong istraktura [2,3,4,5] Hakbang 5.Nagdagdag kami ng '1'. Nagmumula ito sa kanang anak ng 3 hanggang sa kaliwang anak ng 2, at pagkatapos ay napupunta sa ugat. Ang istraktura ng data ng resulta: [1,2,4,5,3] Ang proseso ng Pag-alis ay nagsisimula sa isang ugat, at pinupukaw nito ang mga baligtad na pamamaraan. Kaya, una mayroon kaming 1 bilang isang ugat, pagkatapos ay 2, 3, 4 at sa wakas ay 5. Kaya naman ang paggamit ng pag-alis ng operation poll()

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

nakuha namin ang "pinag-uri-uriin" sa linear na kahulugan na output:

1
2
3
4
5

Kaya maaaring maging epektibo ang priority queue para sa ilang operasyon. Ito ay tumatagal ng oras ng O(log N) upang maipasok at matanggal ang bawat elemento, at maaari mong makuha ang minimal na elemento sa O(1). Narito ang buong halimbawa:

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

Mahalagang maunawaan na ang mga priyoridad na pila ay batay sa mga binary heap, kaya hindi nila pinapanatili ang mga elemento sa linear sorted order. Ang bawat paraan mula sa ugat hanggang sa dahon ay naayos, ngunit ang iba't ibang paraan mula sa ugat ay hindi. Nangangahulugan iyon na maaari mong makuha ang kaunting elemento ng pila nang napakabilis.

Ano ang dapat mong malaman tungkol sa priority queue. Maikling listahan

• Hindi pinapayagan ng Priority Queue ang mga NULL na bagay.
• Maaari ka lamang magdagdag ng mga maihahambing na bagay sa PriorityQueue.
• Ang priyoridad na pila ay binuo bilang isang min heap, isang uri ng binary tree. Ang minimal na elemento ay isang ugat. Ang mga bagay ng priority queue ay inayos bilang default sa natural na pagkakasunud-sunod.
• Maaari mong gamitin ang Comparator kung kailangan mo ng custom na pag-order.
• Ang PriorityQueue ay hindi ligtas sa thread, kaya mas mahusay mong gamitin ang PriorityBlockingQueue upang gumana sa isang kasabay na kapaligiran.
• Nagbibigay ang PriorityQueue ng oras ng O(log(n)) para sa mga paraan ng pagdaragdag at poll at O(1) upang makakuha ng kaunting elemento.