Dubbel prioritetskö
Inom datavetenskap är en dubbeländad prioritetskö (DEPQ) eller dubbeländad heap en datastruktur som liknar en prioritetskö eller heap , men möjliggör effektiv borttagning av både maximum och minimum, enligt någon ordning på tangenterna ( objekt) lagrade i strukturen. Varje element i en DEPQ har en prioritet eller ett värde. I en DEPQ är det möjligt att ta bort elementen i både stigande och fallande ordning.
Operationer
En dubbelsidig prioritetskö innehåller följande operationer:
- isEmpty()
- Kontrollerar om DEPQ är tom och returnerar sant om det är tomt.
- size()
- Returnerar det totala antalet element som finns i DEPQ.
- getMin()
- Returnerar det element som har minst prioritet.
- getMax()
- Returnerar elementet med högsta prioritet.
- put( x )
- Infogar elementet x i DEPQ.
- removeMin()
- Tar bort ett element med lägsta prioritet och returnerar detta element.
- removeMax()
- Tar bort ett element med maximal prioritet och returnerar detta element.
Om en operation ska utföras på två element som har samma prioritet, väljs det element som infogas först. Prioriteten för ett element kan också ändras när det väl har infogats i DEPQ.
Genomförande
Dubbla prioritetsköer kan byggas från balanserade binära sökträd (där minimi- och maxelementen är löv längst till vänster respektive längst till höger), eller med hjälp av specialiserade datastrukturer som min-max-hög och parningshög .
Generiska metoder för att komma till dubbla prioritetsköer från normala prioritetsköer är:
Metod med dubbla strukturer
I denna metod upprätthålls två olika prioritetsköer för min och max. Samma element i båda PQ:erna visas med hjälp av korrespondenspekare. Här är minimum- och maximielementen värden som finns i rotnoderna för min-hög respektive maxhög.
- Ta bort min-elementet : Utför removemin() på min-högen och remove( nodvärde ) på maxhögen, där nodvärde är värdet i motsvarande nod i maxhögen.
- Ta bort maxelementet : Utför removemax() på maxhögen och remove( nodvärde ) på minhögen, där nodvärde är värdet i motsvarande nod i minhögen.
Total korrespondens
Hälften av elementen är i min PQ och den andra hälften i max PQ. Varje element i min PQ har en en-till-en-överensstämmelse med ett element i max PQ. Om antalet element i DEPQ är udda, behålls ett av elementen i en buffert. Prioriteten för varje element i min PQ kommer att vara mindre än eller lika med motsvarande element i max PQ.
Bladkorrespondens
I motsats till en total överensstämmelse bildar i denna metod endast bladelementen i min och max PQ motsvarande en-till-en-par. Det är inte nödvändigt för icke-bladiga element att vara i ett en-till-en korrespondenspar. Om antalet element i DEPQ är udda, behålls ett av elementen i en buffert.
Intervallhögar
Förutom de ovan nämnda korrespondensmetoderna kan DEPQ:er erhållas effektivt med hjälp av intervallhögar. En intervallhög är som en inbäddad min-maxhög där varje nod innehåller två element. Det är ett komplett binärt träd där:
- Det vänstra elementet är mindre än eller lika med det högra elementet.
- Båda elementen definierar ett slutet intervall.
- Intervall som representeras av vilken nod som helst utom roten är ett underintervall till föräldernoden.
- Element på vänster sida definierar en min heap .
- Element på höger sida definierar en maxhög .
Beroende på antalet element är två fall möjliga -
- Jämnt antal element: I det här fallet innehåller varje nod två element, säg p och q , med p ≤ q . Varje nod representeras då av intervallet [ p , q ].
- Udda antal element: I det här fallet innehåller varje nod utom den sista två element som representeras av intervallet [ p , q ] medan den sista noden kommer att innehålla ett enda element och representeras av intervallet [ p , p ].
Infoga ett element
Beroende på antalet element som redan finns i intervallhögen är följande fall möjliga:
- Udda antal element: Om antalet element i intervallhögen är udda, infogas det nya elementet först i den sista noden. Sedan jämförs den successivt med de tidigare nodelementen och testas för att uppfylla kriterierna som är väsentliga för en intervallhög som anges ovan. Om elementet inte uppfyller något av kriterierna, flyttas det från den sista noden till roten tills alla villkor är uppfyllda.
- Jämnt antal element: Om antalet element är jämnt, skapas en extra nod för att infoga ett nytt element. Om elementet faller till vänster om föräldraintervallet anses det vara i minhögen och om elementet faller till höger om förälderintervallet anses det vara i maxhögen . Vidare jämförs den successivt och flyttas från den sista noden till roten tills alla villkor för intervallhög är uppfyllda. Om elementet ligger inom intervallet för själva föräldernoden, stoppas processen då och där själv och flytt av element sker inte.
Tiden som krävs för att infoga ett element beror på antalet rörelser som krävs för att uppfylla alla villkor och är O (log n ) .
Ta bort ett element
- Min-element: I en intervallhög är minimielementet elementet på vänster sida av rotnoden. Detta element tas bort och returneras. För att fylla i den vakans som skapats på vänster sida av rotnoden, tas ett element från den sista noden bort och återinförs i rotnoden. Detta element jämförs sedan successivt med alla de vänstra elementen i de fallande noderna och processen stoppas när alla villkor för en intervallhög är uppfyllda. Om det vänstra elementet i noden blir större än det högra elementet i något skede, byts de två elementen och sedan görs ytterligare jämförelser. Slutligen kommer rotnoden åter att innehålla minimielementet på vänster sida.
- Max element: I en intervallhög är det maximala elementet elementet på höger sida av rotnoden. Detta element tas bort och returneras. För att fylla i den vakans som skapats på höger sida av rotnoden, tas ett element från den sista noden bort och återinförs i rotnoden. Ytterligare jämförelser görs på liknande grunder som diskuterats ovan. Slutligen kommer rotnoden igen att innehålla max-elementet på höger sida.
Sålunda, med intervallhögar, kan både minimum- och maximumelementen tas bort effektivt från rot till blad. Således kan en DEPQ erhållas från en intervallhög där elementen i intervallhögen är prioriteterna för element i DEPQ.
Tidskomplexitet
Intervallhögar
När DEPQ:er implementeras med intervallhögar bestående av n element, formuleras tidskomplexiteten för de olika funktionerna i tabellen nedan
| Drift | Tidskomplexitet |
|---|---|
| i det( ) | På) |
| är tom( ) | O(1) |
| getmin( ) | O(1) |
| getmax( ) | O(1) |
| storlek ( ) | O(1) |
| infoga (x) | O(log n ) |
| removeMin( ) | O(log n ) |
| removeMax( ) | O(log n ) |
Parning av högar
När DEPQ:er implementeras med hjälp av heaps eller parningshögar som består av n element, formuleras tidskomplexiteten för de olika funktionerna i tabellen nedan. För parning av högar är det en amorterad komplexitet .
| Drift | Tidskomplexitet |
|---|---|
| är tom( ) | O(1) |
| getmin( ) | O(1) |
| getmax( ) | O(1) |
| infoga (x) | O(log n ) |
| removeMax( ) | O(log n ) |
| removeMin( ) | O(log n ) |
Ansökningar
Extern sortering
Ett exempel på tillämpning av den dubbelsidiga prioritetskön är extern sortering . I en extern sortering finns det fler element än vad som kan hållas i datorns minne. Elementen som ska sorteras finns initialt på en skiva och den sorterade sekvensen ska lämnas på skivan. Den externa snabbsorteringen implementeras med hjälp av DEPQ enligt följande:
- Läs in så många element som får plats i en intern DEPQ. Elementen i DEPQ kommer så småningom att vara mittgruppen (pivot) av element.
- Läs in de återstående delarna. Om nästa element är ≤ det minsta elementet i DEPQ, mata ut nästa element som en del av den vänstra gruppen. Om nästa element är ≥ det största elementet i DEPQ, mata ut nästa element som en del av den högra gruppen. Annars, ta bort antingen max- eller min-elementet från DEPQ (valet kan göras slumpmässigt eller omväxlande); om max-elementet tas bort, mata ut det som en del av den högra gruppen; annars, mata ut det borttagna elementet som en del av den vänstra gruppen; infoga det nyinmatade elementet i DEPQ.
- Mata ut elementen i DEPQ, i sorterad ordning, som mittgrupp.
- Sortera vänster och höger grupper rekursivt.