Prioritetskø i Java

Anta at du tilbyr service til tre forskjellige personer som står foran deg. Den tredje personen er tilfeldigvis din venn. Tjenesten skal visstnok være førstemelding. Med førstekompetanse-første-serverte, har den første personen størst prioritet; Den andre personen har større prioritet; den tredje personen, jo mindre prioritet, og så videre. Du vil ikke bli straffet, hvis du ikke observerer førstemelding. Du bestemte deg for å tjene vennen din først, deretter den første personen, etterfulgt av den andre personen. Dette betyr at du ga vennen din størst prioritet. Når vi ser på scenariet fra en robots synspunkt, hadde den tredje posisjonen størst prioritet.

Dagen etter kom de samme tre personene. Denne gangen er vennen din i midten. Du bestemte deg for å tjene ham først, foran personen som kom først, deretter den tredje personen, og til slutt, den første personen. Så denne gangen, ifølge roboten, har posisjon 2 størst prioritet, etterfulgt av stilling 3.

På den tredje dagen er vennen din først, og du gjør første-til-first-serverte. Konklusjonen fra noen og roboten er at prioritet avhenger av hvem som er bekymret og av hver persons stilling. Merk: I det virkelige liv avhenger ikke alltid prioritet.

I programmering er en binær prioriteringskø der den første varen har størst prioritet. Det tredje elementet kan ha større prioritet, og det andre elementet, den tredje prioriteten. Prioriterte køer er av binær karakter. Merk: Det første elementet er alltid den største prioriteten i en prioriteringskø. Det kan også hende at den andre varen har større prioritet og den tredje varen har tredje prioritet. I definisjonen av prioriteringskøen kan det hende at prioriteringene til andre og tredje elementer ikke er i synkende rekkefølge. Denne forskjellen fortsetter ned i køen til det siste elementet, som kanskje ikke er minst prioritert vare. Imidlertid vil det være blant de med laveste prioritet. Denne delvis-sorten er også kjent som delvis bestilling. Så en prioriteringskø er en kø med delvis bestilling, der prioritet ikke er første-til-first-serverte, selv om det er den generelle regelen.

Når du arbeider med matrisen, er første-til-come_first-serverte først-in_first-out, skrevet som FIFO. I databehandling er køen FIFO, mens prioriteringskøen er en delvis FIFO, fordi køen er synkende, har noen elementer prioriteringer større enn de nærmeste forgjengerne. Når prioriteringskøen synker ytterligere, øker avstanden mellom slike nær forgjengerne og de høyere prioriteringene.

En prioritert kø implementeres som en datastruktur. Det neste spørsmålet er, hva er en haug? Det er maksimal haug og minimumshaugen, som vil bli diskutert i detalj nedenfor.

Artikkelinnhold

• HAP -datastruktur
• Prioritetskø i Java riktig
• Java konstruksjon av en prioriteringskø
• Java -metoder for en prioriteringskø
• Konklusjon

HAP -datastruktur

Det er maksimal, og det er min-heap. Med Max-Heap er den første varen den største verdien. Når køen er avstammet, fortsetter verdiene å redusere, øke og generelt redusere. Med Min-Heap er den første varen den minste verdien. Når køen går ned, fortsetter verdiene å øke og redusere og øke generelt. Verdiene til en haug kan oppbevares i en matrise.

En binær haug er der en node (vare) har to barn. Det første barnet er det venstre barnet og det andre barnet er det rette barnet. Verdien av en hvilken som helst node kalles en nøkkel.

Max-heap

Følgende liste er en max-heap som allerede er delvis bestilt og ikke trenger ytterligere bestilling:

89, 85, 87, 84, 82, 79, 73, 80, 81 ,,, 65, 69

89 er den første verdien ved indeks 0. Det er rotnoden (rotforelder). Det er den største verdien blant alle verdiene. Det første barnet (85) er ved indeks 1, hvis indeks er lik 2 (0) + 1, hvor 0 er indeksen for foreldrene. Det andre barnet (87) er ved indeks 2, som er lik 2 (0) + 2, der 0 er indeksen for foreldrene.

85 er ved indeks 1. Det er en forelder. Det første barnet (84) er på indeks 3, som er lik 2 (1) + 1, der 1 er indeksen for foreldrene. Det andre barnet (82) er ved indeks 4, som er lik 2 (1) + 2, der 1 er indeksen for foreldrene.

87 er ved indeks 2. Det er en forelder. Det første barnet (79) er ved indeks 5, som er lik 2 (2) + 1, der 2 er indeksen for foreldrene. Det andre barnet (73) er ved indeks 6, som er lik 2 (2) + 2, der 2 er indeksen for foreldrene.

Generelt, når indekstellingen begynner fra 0, la jeg representere indeksen til en forelder av matrisen; Og så, venstre (første) barn av en forelder på indeks I er ved indeks 2i + 1; og dets høyre (andre) barn, er på indeks 2i + 2. Noen celler mot slutten av matrisen kan være tomme; De må ikke ha verdier.

Den forrige listen er et godt eksempel på innholdet i en prioriteringskø etter at all inkludering av elementer er fullført. Hvis det første elementet fjernes, blir resten omorganisert for å få verdiene oppsett, og danner en ny prioriteringskø. På den måten vil det vises å fjerne alle elementene fra toppen som om alle elementene ble sortert ordentlig. Elementene kan fremdeles fås som de er, i delvis rekkefølge, uten å fjerne noe element.

Min-heap

Min-heap er det motsatte av maksimal.

Prioritetskø i Java riktig

Java har en klasse som heter PriorityQueue, for prioritert Queue. Det har mange konstruktører og metoder. Bare tre konstruktører og de mer passende metodene er forklart nedenfor:

Java konstruksjon av en prioriteringskø

Public PriorityQueue ()

Dette skaper en prioriteringskø uten noe element. Klassen, PriorityQueue, er i Java.util.* pakke, som må importeres. Følgende kodesegment oppretter en tom prioritering og legger deretter til usorterte (ikke engang delvis sorterte) verdier i køen:

PriorityQueue PQ = Ny prioritering();
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85);

Disse tallene er alle heltall. De er fra den delvis sorterte listen gitt ovenfor, men for øyeblikket er de helt usortert når de er lagt inn. Elementene i PQ er nå delvis sortert i henhold til definisjonen av prioriteringskøen i Java.

Public PriorityQueue (PriorityQueue C)

Dette skaper en prioritering fra en annen prioritering. Følgende kodesegment illustrerer dette:

PriorityQueue PQ = Ny prioritering();
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85);
PriorityQueue pq1 = ny prioritering(PQ);

PQ1 er opprettet fra PQ. Den har for øyeblikket den samme delvise ordren og PQ.

Den tredje konstruktørmetoden er illustrert nedenfor.

Java -metoder for en prioriteringskø

Offentlig int -størrelse ()

Dette returnerer størrelsen på listen, og inkluderer ikke tomme celler, som illustrert i følgende kode:

PriorityQueue PQ = Ny prioritering();
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85);
int sz = pq.størrelse();
System.ute.Println (SZ);

Utgangen er 11.

Offentlig tomrom foreach (forbrukerhandling)

Denne metoden må brukes på en spesiell måte for å kopiere ut alle verdiene i prioriteringskøen i delvis sortert form. Følgende program illustrerer dette:

PriorityQueue PQ = Ny prioritering();
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85);
pq.Foreach (vare -> System.ute.print (element + ""));
System.ute.println ();

Legg merke til hvordan koden i parentesene til foreach -metoden er laget. Varen er en dummyvariabel som representerer hvert element i køen. Legg merke til bruken av piloperatøren. Utgangen er:

65 69 84 79 73 87 89 80 81 82 85

Utgangen er riktig, i delvis rekkefølge, men i en stigende rekkefølge. Dette er ikke nødvendigvis den omvendte rekkefølgen gitt ovenfor på grunn av måten verdiene ble inkludert på listen. Det vil si at foreach-metoden returnerer listen som en min-heap. For å returnere listen i synkende rekkefølge, bruk følgende konstruktør:

Public PriorityQueue (Comparator Comparator)

Dette er en konstruktør. Følgende kode viser hvordan du bruker den:

PriorityQueue PQ = Ny prioritering((x, y) -> heltall.sammenligne (y, x));
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85);
pq.Foreach (vare -> System.ute.print (element + ""));

X, y er dummyvariabler som representerer de mindre og mindre verdiene. Merk at i de første parentesene for x og y kommer x før y. I de andre parentesene kommer y før x. Utgangen er:

89 85 87 80 82 69 84 65 79 73 81

Offentlig boolsk add (e e)

Antall elementer i en prioriteringskø kan økes en etter en. Denne metoden returnerer sann hvis en endring skjedde; og falsk ellers. Følgende kode legger til den tolvte praktiske verdien i køen:

PriorityQueue PQ = Ny prioritering((x, y) -> heltall.sammenligne (y, x));
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85); pq.Legg til (70);
pq.Foreach (vare -> System.ute.print (element + ""));

Merverdien ville bevege seg opp i køen for å passe seg selv på passende posisjon, noe som fører til en viss omjustering av elementstillinger. Utgangen er:

89 85 87 80 82 70 84 65 79 73 81 69

Offentlig E -avstemning ()

Denne metoden henter og fjerner hodet på køen; eller returnerer null, hvis denne køen er tom. Hver gang hodet fjernes, justerer prioriteringskøen seg for å ha et nytt rettmessig hode. Hvis hodet fortsetter å bli fjernet, vil de returnerte verdiene være i fullstendig sortert ordre. Følgende kode illustrerer dette:

PriorityQueue PQ = Ny prioritering((x, y) -> heltall.sammenligne (y, x));
pq.Legg til (69); pq.Legg til (65); pq.Legg til (87); pq.Legg til (79);
pq.Legg til (73); pq.Legg til (84); pq.Legg til (89); pq.Legg til (80);
pq.Legg til (81); pq.Legg til (82); pq.Legg til (85); pq.Legg til (70);
pq.Foreach (vare -> System.ute.Trykk (PQ.POLL () + ""));

Utgangen fra forfatterens datamaskin er:

89 87 85 84 82 81 80 79 73 70 69 65 unntak i tråd "Main" Java.util.Samtidig modifisering av opptak
hos Java.base/java.util.PriorityQueue.Foreach (PriorityQueue.Java: 984)
på Theclass.Hoved (TheClass.Java: 11)

Merk at utgangen er av fullstendig sortert ordre. Denne spesielle koden kunne ikke fange unntaket som ble kastet inn. Dette problemet er igjen som en forskningsøvelse for leseren.

Konklusjon

En prioritert kø i Java er en kø der elementer har prioritert annet enn FIFO. En prioritert kø er vanligvis en haug, som kan være maksimal hau eller minimumshap. Verdiene må være av samme type. De er lagret i køen i heapformat (delvis bestilling). Vi håper du fant denne artikkelen nyttig. Sjekk ut de andre Linux -hint -artiklene for tips og opplæringsprogrammer.