PriorityQueue i Java forklaret med eksempler
I Java er en prioritetskø en speciel form for køen, hvori alle komponenter er bestilt enten efter deres naturlige rækkefølge eller af en tilpasset Comparator, der leveres på konstruktionstidspunktet. Før vi taler om prioriterede køer, lad os se på, hvad en almindelig kø er.
Den første ind, først ud (FIFO) struktur bruges i en typisk kø. Hvis tre beskeder – m1, m2 og m3 – kommer ind i køen i den rækkefølge, afsluttes de i samme rækkefølge.
Hvad er formålet med køer?
Lad os forestille os, at vi har meget hurtige datageneratorer (for eksempel når en bruger klikker på en webside). Vi agter dog at indtage disse data langsommere senere. I dette scenarie ville producenten sende alle beskeder til køen, og en forbruger ville forbruge dem i en langsommere hastighed senere fra køen.
I henhold til den givne rækkefølge inkluderer forsiden af prioritetskøen det mindste element, og bagsiden af prioritetskøen har det største element.
Ifølge den angivne bestilling fjernes det mindst vigtige element først ved fjernelse af et element fra prioritetskøen. Priority Queue-klassen implementerer Queue-grænsefladen og er en del af Javas samlingssystem. Klassen Priority Queue i Java har følgende klassestruktur.
Følgende er nogle vigtige faktorer, du skal huske om Prioritetskø:
- Null er ikke tilladt i PriorityQueue.
- Vi kan ikke etablere en Priority Queue af ikke-sammenlignelige objekter.
- Ubundne køer er Prioritetskøer.
- Den sidste post i den angivne rækkefølge er øverst i denne kø. Hvis der er talrige komponenter bundet til den laveste værdi, er hovedet et af de – bånd, der er brudt tilfældigt.
- Fordi PriorityQueue ikke er trådsikker, giver Java en løsning.
- I et Java multithreading-miljø implementerer PriorityBlockingQueue-klassen BlockingQueue-grænsefladen.
- Afstemnings-, sletnings-, kig- og elementprocedurerne får alle adgang til elementet øverst i køen.
- Tilføje- og afstemningsteknikkerne tager O(log(n))-tid.
- AbstractQueue, AbstractCollection, Collection og Object har alle metoder, som de arver.
Sammensætning af en prioriteret kø
Lad os konstruere en heltalsprioritetskø og tilføje nogle heltal til den. Efter at have tilføjet heltal til prioritetskøen, fjerner vi dem for at bemærke, hvordan det mindste heltal bliver slettet først, derefter det næstmindste heltal og så videre.
import java.util.PriorityQueue;
public class CodePriorityQueue {
public static void main(String[] args) {
// Create a Priority Queue
PriorityQueue<Integer> numPQ = new PriorityQueue<>();
// Add items to a Priority Queue (ENQUEUE)
numPQ.add(120);
numPQ.add(90);
numPQ.add(10);
numPQ.add(89);
// Removing Priority Queue (DEQUEUE) items
while (!numPQ.isEmpty()) {
System.out.println(numPQ.remove());
}
}
} Lad os se på det identiske scenarie ved hjælp af en strengprioritetskø.
import java.util.PriorityQueue;
public class CodePriorityQueueString {
public static void main(String[] args) {
// Creation of a Priority Queue
PriorityQueue<String> stringPQ = new PriorityQueue<>();
// Add items to a Priority Queue (ENQUEUE)
stringPQ.add("Apple");
stringPQ.add("Mango");
stringPQ.add("Quava");
stringPQ.add("Pineapple");
stringPQ.add("Banana");
stringPQ.add("Peas");
// Removing Priority Queue (DEQUEUE) Items
while (!stringPQ.isEmpty()) {
System.out.println(stringPQ.remove());
}
}
} I dette scenarie bliver den mindste streng slettet først i henhold til den naturlige rækkefølge af strenge.
Brug af en tilpasset komparator til at oprette en prioriteret kø
Antag, at vi skal etablere en prioritetskø af strengelementer, hvor den korteste streng behandles først. Vi kan etablere en sådan prioritetskø ved at sende en brugerdefineret komparator, der sammenligner to strenge efter længde. Her er en illustration:
import java.util.Comparator;
import java.util.PriorityQueue;
public class CodePriorityQueueCustomComparator {
public static void main(String[] args) {
// A custom comparator that compares the lengths of two Strings.
Comparator<String> strLengthComparator = new Comparator<String>() {
@Override
public int compare(String strOne, String strTwo) {
return strOne.length() - strTwo.length();
}
};
/*
A lambda expression like this can be used to build the above Comparator=>
Comparator<String> strLengthComparator = (strOne, strTwo) -> {
return strOne.length() - strTwo.length();
};
Which can be condensed even more in the following way: =>
Comparator<String> strLengthComparator = Comparator.comparingInt(String::length);
*/
// Create a custom Comparator for a Priority Queue.
PriorityQueue<String> laptopPQ = new PriorityQueue<>(stringLengthComparator);
// Add items to a Priority Queue (ENQUEUE)
laptopPQ.add("HP");
laptopPQ.add("DELL");
laptopPQ.add("IBM");
laptopPQ.add("Chrome Book");
laptopPQ.add("Lenovo");
laptopPQ.add("Toshiba");
// Removing Priority Queue (DEQUEUE) Items
while (!laptopPQ.isEmpty()) {
System.out.println(laptopPQ.remove());
}
}
} Vær opmærksom på, hvordan den korteste streng slettes først.
Brugerdefineret objektprioritetskø
Brugerdefinerede ordrer er også tilgængelige, og vi kan opnå det ved hjælp af en komparator. Lad os starte med at lave en heltalsprioritetskø. Men denne gang, lad os sortere resultaterne efter værdi i faldende rækkefølge. For at opnå dette skal vi først konstruere en heltalskomparator:
static class CodeCustomIntegerComparator implements Comparator<Integer> {
@Override
public int compare(Integer intOne, Integer intTwo) {
return intOne < intTwo ? 1 : -1;
}
}
Vi implementerer komparatorgrænsefladen og tilsidesætter sammenligningsmetoden for at skabe en komparator. Vi kan hente resultatet i faldende rækkefølge ved at bruge intOne
Queue<Integer> codeIntPQ = new PriorityQueue<>(new CustomIntegerComparator());
Den resterende kode, som tilføjer elementer til prioritetskøen og udskriver dem, er som følger:
codeIntPQ.add(11);
codeIntPQ.add(5);
codeIntPQ.add(-1);
codeIntPQ.add(12);
codeIntPQ.add(6);
System.out.println("In a Priority Queue, integers are kept in reverse order of priority. \n");
while (!codeIntPQ.isEmpty()) {
System.out.println(codeIntPQ.poll());
} Vi kan konstatere, at komparatoren gjorde et godt stykke arbejde. Heltallene bliver nu leveret i faldende rækkefølge via prioritetskøen. I dette eksempel lærer du, hvordan du opretter en prioriteret kø af brugerdefinerede elementer.
Fordi en prioritetskø skal sammenligne og organisere dens indhold, skal den brugerspecificerede klasse implementere den sammenlignelige grænseflade. Eller en komparator skal leveres, når prioritetskøen oprettes. Hvis du tilføjer nye objekter til prioritetskøen, vil det kaste en ClassCastException.
Tag et kig på eksemplet nedenfor, hvor vi etablerer en prioritetskø for en tilpasset klasse kaldet Medarbejder. Medarbejderklassen bruger den sammenlignelige grænseflade til at sammenligne lønningerne for to ansatte.
import java.util.Objects;
import java.util.PriorityQueue;
class CodeEmployee implements Comparable<Employee> {
private String fName;
private String mName;
private double salary;
public CodeEmployee(String fName, String mName, double salary) {
this.fName = fName;
this.mName = mName;
this.salary = salary;
}
public String getFName() {
return fName;
}
public void setFName(String fName) {
this.fName = fName;
}
public String getMName() {
return mName;
}
public void setMName(String mName) {
this.mName = mName;
}
public double getSalary() {
return salary;
}
public void setSalary(double salary) {
this.salary = salary;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Employee employee = (Employee) o;
return Double.compare(employee.salary, salary) == 0 &&
Objects.equals(name, employee.name);
}
@Override
public int hashCode() {
return Objects.hash(name, salary);
}
@Override
public String toString() {
return "CodeEmployee{" +
"name='" + name + '\'' +
", salary=" + salary +
'}';
}
// Comparing two code employee objects based on their salaries
@Override
public int compareTo( CodeEmployee cEmployee) {
if(this.getSalary() > cEmployee.getSalary()) {
return 1;
} else if (this.getSalary() < employee.getSalary()) {
return -1;
} else {
return 0;
}
}
}
public class UserDefinedPriorityQueueObject {
public static void main(String[] args) {
/*
A PriorityQueue with user-defined items is required because
1. Either the Comparable interface should be implemented, or the compareTo() function should be implemented.
2. Alternatively, while constructing the PriorityQueue, you should give a custom Comparator.
*/
// Create a PriorityQueue
PriorityQueue<CodeEmployee> employeePQ = new PriorityQueue<>();
// Add items to the Priority Queue
employeePQ.add(new CodeEmployee("Ken", 90000.00));
employeePQ.add(new CodeEmployee("Joy", 190000.00));
employeePQ.add(new CodeEmployee("Paul", 55000.00));
employeePQ.add(new CodeEmployee("Green", 37000.00));
/*
The Employee class's compareTo() method establishes the order in which the objects should be dequeued.
*/
while (!employeePQ.isEmpty()) {
System.out.println(employeePQ.remove());
}
}
} Vær opmærksom på, hvordan kodemedarbejderen med den laveste løn er den første, der bliver fyret.
Java-objekter i en prioriteret kø
Vi har set, hvordan man bruger strenge og heltal med prioritetskøer indtil dette tidspunkt. Prioritetskøer, der indeholder tilpassede Java-objekter, bruges almindeligvis i applikationer fra den virkelige verden. Lad os starte med at lave en EcommerceOrder-klasse til at opbevare kundeordreoplysninger:
public class EcommerceOrder implements Comparable<EcommerceOrder> {
private int ordId;
private double ordAmount;
private String customerName;
public EcommerceOrder(int ordId, double ordAmount, String customerName) {
this.ordId = ordId;
this.orderAmount = ordAmount;
this.customerName = customerName;
}
@Override
public int compareTo( EcommerceOrder o) {
return o.orderId > this.ordId? 1 : -1;
}
@Override
public String toString() {
return "ordId:" + this.ordId + ", ordAmount:" + this.ordAmount + ", customerName:" + customerName;
}
public double getOrderAmount() {
return ordAmount;
}
}
Det er en ligetil Java-klasse til at holde styr på kundeordrer. Denne klasse implementerer en lignende grænseflade, hvilket giver os mulighed for at vælge, hvordan dette element skal prioriteres i prioritetskøen. CompareTo-funktionen i ovenstående kode bestemmer rækkefølgen. Linjen o.ordId> this.ordId ?1:-1 angiver, at ordrerne skal sorteres i ordId-feltets faldende rækkefølge.
Koden, der opbygger en prioritetskø for EcommerceOrder-objektet, er som følger:
EcommerceOrder ecommerceOrder1 = new EcommerceOrder(1, 189.0, "Client One");
EcommerceOrder ecommerceOrder2 = new EcommerceOrder(3, 87.0, "Client Three");
EcommerceOrder ecommerceOrder3 = new EcommerceOrder(2, 260.0, "Client Two");
Queue<EcommerceOrder> ecommerceClientOrders = new PriorityQueue<>();
ecommerceClientOrders.add(ecommerceOrder1);
ecommerceClientOrders.add(ecommerceOrder2);
ecommerceClientOrders.add(ecommerceOrder3);
while (!ecommerceClientOrders.isEmpty()) {
System.out.println(ecommerceClientOrders .poll());
} Tre e-handelsordrer er blevet lavet og tilføjet til prioritetskøen i koden ovenfor. Vi modtager følgende output, når vi kører denne kode:
ordId:3, ordAmount:87.0, customerName: Client Three ordId:2, ordAmount:260.0, customerName: Client Two ordId:1, ordAmount:189.0, customerName: Client One
Resultatet er i faldende orden efter ordId, som tilsigtet.
Prioritering baseret på ordAmount-parameteren
Dette er endnu en sand historie. Lad os sige, at ordId prioriterer eCommerceClientOrder-objektet som standard. Vi har dog brug for midlerne til at prioritere baseret på ordrebeløb. Du forestiller dig måske, at vi kan redigere eCommerceOrder-klassens compareTo-funktion til ordre baseret på ordAmount.
Men fordi eCommerceOrder-klassen bruges forskellige steder i hele applikationen, vil en direkte ændring af compareTo-funktionen forårsage problemer andre steder. Svaret er enkelt:Vi kan konstruere en ny tilpasset komparator til eCommerceOrder-klassen og bruge den sammen med prioritetskøen. Koden for den brugerdefinerede komparator er som følger:
static class eCommerceOrderComparator implements eCustomComparator<EcommerceOrder> {
@Override
public int compare( EcommerceOrder ordOne, EcommerceOrder ordTwo)
{
return ordOne.getOrderAmount() < ordTwo.getOrderAmount() ? 1 : -1;
}
} Det ligner meget den tilpassede heltalskomparator, vi så før.
Linjen ordOne.getOrderAmount()
I den foregående kode sendes komparatoren til prioritetskøen i næste linje:
Efter at have kørt denne kode får vi følgende resultat:
Vi kan se, at dataene er sorteret efter ordAmount i faldende rækkefølge.
Det mindste eller mindste element er forrest i køen i den naturlige rækkefølge af Prioritetskøen. Som følge heraf er rækkefølgen stigende. Med stigende rækkefølge af komponenter er dette kendt som "Min prioritetskøen." Java-programmet nedenfor viser, hvordan Min Priority Queue er implementeret i Java.
Elementerne i min prioritetskøen er i stigende rækkefølge. I modsætning hertil er elementerne i max prioritetskøen i faldende rækkefølge, dvs. hovedet af Max prioritetskøen returnerer det største element i køen. Kodestykket nedenfor viser, hvordan du bruger Java Max Priority Queue.
Her er noget kode, der viser, hvordan man laver en simpel strengprioritetskø.
Vi tilføjede et par heltal til køen i vilkårlig rækkefølge i eksemplet ovenfor. Komponenterne blev derefter udskrevet, når jeg itererede over køen. Som du kan se ovenfor, gemmes varerne ikke i sorteret rækkefølge. Som tidligere nævnt garanterer binær heap kun semi-ordening:elementer i øvre noder er flere (eller færre) end dem i nedre noder. For eksempel i en max-heap er forældre altid større end deres børn. Dynger, i modsætning til binære søgetræer, holder ikke absolut venstre-til-højre rækkefølge.
I denne artikel lærte du, hvad en prioritetskø er, hvordan man bruger en, hvordan man opretter en med en tilpasset komparator, og hvordan man inkluderer brugerdefinerede objekter i en prioritetskø.
En PriorityQueue er en køtype, der tillader Java-programmører at indsætte komponenter i en hvilken som helst rækkefølge, men hente dem i en foruddefineret (sorteret) rækkefølge. Prioritetskøens elementer sorteres ved hjælp af en komparator, der blev leveret, da køen blev bygget.
PriorityQueue er en værdifuld indbygget samling, som bør være bekendt for alle Java-udviklere. Du har et ekstra værktøj i dit værktøjssæt til at designe effektive applikationer, når du har lært det.
Når du lærer om prioriterede køer, er det afgørende at forstå de grundlæggende ideer, som er ret enkle og hjælper dig med at træffe informerede designbeslutninger. EcommerceOrder eCommerceOne = new EcommerceOrder(1, 100.0, "eCommerce Client1");
EcommerceOrder eCommerceTwo = new EcommerceOrder(3, 50.0, "eCommerce Client3");
EcommerceOrder eCommerceThree = new EcommerceOrder(2, 300.0, "eCommerce Client2");
Queue<EcommerceOrder> eClientOrders = new PriorityQueue<>(new CustomerOrderComparator());
eClientOrders.add(eCommerceOne);
eClientOrders.add(eCommerceTwo);
eClientOrders.add(eCommerceThree);
while (!eClientOrders.isEmpty()) {
System.out.println(eClientOrders.poll());
} Queue<EcommerceOrder> eClientOrders = new PriorityQueue<>(new eCommerceOrderComparator());
ordId:2, ordAmount:300.0, customerName:customer2
ordId:1, ordAmount:100.0, customerName:customer1
ordId:3, ordAmount:50.0, customerName:customer3
Javas minimumsprioritetskø
import java.util.*;
class Main{
public static void main(String args[]){
//Create a PriorityQueue object with the default ordering.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
// add a priority queue element
priorityQueue.add(18);
priorityQueue.add(16);
priorityQueue.add(14);
priorityQueue.add(12);
priorityQueue.add(22);
priorityQueue.add(20);
//show the minimum PriorityQueue
System.out.println("The minimum contents of the Priority Queue (natural ordering):");
Integer val = null;
while( (val = priorityQueue.poll()) != null) {
System.out.print(val + " ");
}
}
} Javas maksimale prioritetskø
import java.util.*;
class Main{
public static void main(String args[]){
//To generate the maximum PQ, declare a PriorityQueue object with a custom comparator.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer lhs, Integer rhs) {
if (lhs < rhs) return +1;
if (lhs.equals(rhs)) return 0;
return -1;
}
});
//add element to the PriorityQueue
priorityQueue.add(8);
priorityQueue.add(6);
priorityQueue.add(4);
priorityQueue.add(2);
priorityQueue.add(12);
priorityQueue.add(10);
//showing the max PriorityQueue
System.out.println("The max Priority Queue contents:");
Integer val = null;
while( (val = priorityQueue.poll()) != null) {
System.out.print(val + " ");
}
}
} Eksempel:Naturlig rækkefølgeprioritetskøer
private static void CodeStringNaturalOrdering() {
Queue<String> codeStringsPQ = new PriorityQueue<>();
codeStringsPQ.add("mango");
codeStringsPQ.add("apple");
codeStringsPQ.add("banana");
codeStringsPQ.add("peas");
codeStringsPQ.add("quavas");
System.out.println("Strings in a Priority Queue Stored in Natural Order \n");
while (!codeStringsPQ.isEmpty()) {
System.out.println(codeStringsPQ.poll());
}
} Eksempel:Prioritetskøer i Java
package com.code.underscored;
import java.util.PriorityQueue;
public class CodePriorityQueue {
public static void main(String[] args) {
// Create a PriorityQueue to sort things according to their natural order.
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// Let's fill in some gaps in the PriorityQueue.
Integer [] elements = new Integer[]{108, 200, 198, 110, 102,
115, 145, 125, 176, 103, 109, 101, 163, };
for (int e: elements) {
priorityQueue.add(e);
}
// Let's go over the elements one by one to see if they're all stored in the same order.
System.out.print("Iterative printing: ");
for(int e: priorityQueue) {
System.out.print(e + " ");
}
System.out.println();
System.out.print("Retrieval Printing: ");
// Remove each element one by one.
while (!priorityQueue.isEmpty()) {
System.out.print(priorityQueue.remove() + " ");
}
}
} Eksempel:Priority Queue Comparator
import java.util.*;
public class Main {
public static void main(String[] args) {
// A custom comparator that compares the lengths of two Strings.
Comparator<String> codeComparator = new Comparator<String>() {
@Override
public int compare(String strOne, String strTwo) {
return strOne.length() - strTwo.length();
}
};
// Creation of a custom Comparator for a Priority Queue.
PriorityQueue<String> fruitsPQ = new PriorityQueue<>(codeComparator);
// Addition of items to a Priority Queue
fruitsPQ.add("Apple");
fruitsPQ.add("Mango");
fruitsPQ.add("Peas");
fruitsPQ.add("Guava");
fruitsPQ.add("Banana");
fruitsPQ.add("Lemon");
// Printing all elements
System.out.println("\nThe PriorityQueue elements with custom Comparator:");
Iterator iter = fruitsPQ.iterator();
while (iter.hasNext())
System.out.print(iter.next() + " ");
}
} Eksempel:metoder til PriorityQueue ved hjælp af et Java-program
import java.util.*;
class Codeunderscored {
public static void main(String args[]) {
// Creating empty priority queue
PriorityQueue<String> numPQ = new PriorityQueue<String>();
// add elements to numQueue using add()
numPQ.add("Five");
numPQ.add("One");
numPQ.add("Seven");
numPQ.add("Three");
numPQ.add("Eleven");
numPQ.add("Nine");
// Print the head element using Peek () method
System.out.println("Head element is using the peek method:" + numPQ.peek());
// Printing all elements
System.out.println("\n\nThe PriorityQueue elements:");
Iterator iter = numPQ.iterator();
while (iter.hasNext())
System.out.print(iter.next() + " ");
// remove head with poll ()
numPQ.poll();
System.out.println("\n\nAfter removing an element" + "with poll function:");
Iterator<String> iterTwo = numPQ.iterator();
while (iterTwo.hasNext())
System.out.print(iterTwo.next() + " ");
// Removing 'five' using the method remove ()
numQueue.remove("five");
System.out.println("\n\nElement 'five' with"
+ " remove function:");
Iterator<String> iterThree = numQueue.iterator();
while (iterThree.hasNext())
System.out.print(iterThree.next() + " ");
// Use contains to see if an element is present in PriorityQueue ()
boolean ret_val = numPQ.contains("Five");
System.out.println("\n\nPriority queue contains 'Five' "
+ "or not?: " + ret_val);
// toArray returns the array equivalent of PriorityQueue ()
Object[] numArr = numPQ.toArray();
System.out.println("\nArray Contents: ");
for (int i = 0; i < numArr.length; i++)
System.out.print(numArr[i].toString() + " ");
}
}
Konklusion
