Een prioriteitswachtrij is een abstract gegevenstype dat zich op dezelfde manier gedraagt als de normale wachtrij, behalve dat elk element een bepaalde prioriteit heeft, dat wil zeggen dat het element met de hoogste prioriteit op de eerste plaats komt in een prioriteitswachtrij. De prioriteit van de elementen in een prioriteitswachtrij bepaalt de volgorde waarin elementen uit de prioriteitswachtrij worden verwijderd.
De prioriteitswachtrij ondersteunt alleen vergelijkbare elementen, wat betekent dat de elementen in oplopende of aflopende volgorde zijn gerangschikt.
theelepel formaat
Stel bijvoorbeeld dat we waarden zoals 1, 3, 4, 8, 14, 22 in een prioriteitswachtrij hebben ingevoegd, waarbij de volgorde van de waarden van klein naar groot is. Daarom heeft nummer 1 de hoogste prioriteit, terwijl nummer 22 de laagste prioriteit heeft.
Kenmerken van een prioriteitswachtrij
Een prioriteitswachtrij is een uitbreiding van een wachtrij die de volgende kenmerken bevat:
- Aan elk element in een prioriteitswachtrij is een bepaalde prioriteit gekoppeld.
- Een element met de hogere prioriteit wordt verwijderd voordat de lagere prioriteit wordt verwijderd.
- Als twee elementen in een prioriteitswachtrij dezelfde prioriteit hebben, worden ze gerangschikt volgens het FIFO-principe.
Laten we de prioriteitswachtrij begrijpen aan de hand van een voorbeeld.
We hebben een prioriteitswachtrij die de volgende waarden bevat:
1, 3, 4, 8, 14, 22
Alle waarden zijn in oplopende volgorde gerangschikt. Nu zullen we zien hoe de prioriteitswachtrij eruit zal zien na het uitvoeren van de volgende bewerkingen:
Soorten prioriteitswachtrijen
Er zijn twee soorten prioriteitswachtrijen:
Weergave van prioriteitswachtrij
Nu zullen we zien hoe we de prioriteitswachtrij kunnen weergeven via een eenrichtingslijst.
We zullen de prioriteitswachtrij maken met behulp van de onderstaande lijst waarin INFO lijst bevat de gegevenselementen, PRN lijst bevat de prioriteitsnummers van elk gegevenselement dat beschikbaar is in de INFO lijst, en LINK bevat feitelijk het adres van het volgende knooppunt.
Laten we stap voor stap de prioriteitswachtrij maken.
java sorteer arraylist
In het geval van een prioriteitswachtrij wordt het nummer met een lagere prioriteit beschouwd als de hogere prioriteit, d.w.z. nummer met lagere prioriteit = hogere prioriteit.
Stap 1: In de lijst is het lagere prioriteitsnummer 1, waarvan de gegevenswaarde 333 is, dus het wordt in de lijst ingevoegd zoals weergegeven in het onderstaande diagram:
Stap 2: Na het invoegen van 333 heeft prioriteitsnummer 2 een hogere prioriteit, en de gegevenswaarden die bij deze prioriteit horen zijn 222 en 111. Deze gegevens worden dus ingevoegd op basis van het FIFO-principe; daarom wordt eerst 222 toegevoegd en daarna 111.
Stap 3: Na het invoegen van de elementen met prioriteit 2 is het volgende hogere prioriteitsnummer 4 en zijn de data-elementen die zijn geassocieerd met 4 prioriteitsnummers 444, 555, 777. In dit geval zouden elementen worden ingevoegd op basis van het FIFO-principe; daarom wordt eerst 444 toegevoegd, vervolgens 555 en vervolgens 777.
Stap 4: Na het invoegen van de elementen met prioriteit 4 is het eerstvolgende hogere prioriteitsnummer 5, en de waarde die bij prioriteit 5 hoort is 666, dus deze wordt aan het einde van de wachtrij ingevoegd.
Implementatie van Prioriteitswachtrij
De prioriteitswachtrij kan op vier manieren worden geïmplementeerd, waaronder arrays, gekoppelde lijsten, heap-gegevensstructuur en binaire zoekboom. De heap-gegevensstructuur is de meest efficiënte manier om de prioriteitswachtrij te implementeren. Daarom zullen we in dit onderwerp de prioriteitswachtrij implementeren met behulp van een heap-gegevensstructuur. Nu begrijpen we eerst de reden waarom heap de meest efficiënte manier is tussen alle andere datastructuren.
Analyse van complexiteiten met behulp van verschillende implementaties
| Implementatie | toevoegen | Verwijderen | kijkje |
| Gekoppelde lijst | O(1) | Op) | Op) |
| Binaire hoop | O(login) | O(login) | O(1) |
| Binaire zoekboom | O(login) | O(login) | O(1) |
Wat is Hoop?
Een heap is een op een boom gebaseerde gegevensstructuur die een volledige binaire boom vormt en voldoet aan de heap-eigenschap. Als A een ouderknooppunt van B is, wordt A geordend ten opzichte van knooppunt B voor alle knooppunten A en B in een hoop. Het betekent dat de waarde van het bovenliggende knooppunt groter kan zijn dan of gelijk is aan de waarde van het onderliggende knooppunt, of dat de waarde van het bovenliggende knooppunt kleiner kan zijn dan of gelijk is aan de waarde van het onderliggende knooppunt. Daarom kunnen we zeggen dat er twee soorten hopen zijn:
Beide heaps zijn de binaire heap, omdat elk precies twee onderliggende knooppunten heeft.
Prioritaire wachtrijbewerkingen
De gebruikelijke bewerkingen die we kunnen uitvoeren op een prioriteitswachtrij zijn invoegen, verwijderen en bekijken. Laten we eens kijken hoe we de heap-gegevensstructuur kunnen behouden.
Als we een element in een prioriteitswachtrij invoegen, wordt het naar het lege slot verplaatst door van boven naar beneden en van links naar rechts te kijken.
een string naar datum converteren
Als het element niet op de juiste plaats staat, wordt het vergeleken met het bovenliggende knooppunt; als blijkt dat het niet in orde is, worden elementen verwisseld. Dit proces gaat door totdat het element op de juiste positie wordt geplaatst.
Zoals we weten is het maximale element in een maximale heap het hoofdknooppunt. Wanneer we het hoofdknooppunt verwijderen, ontstaat er een leeg slot. Het laatst ingevoegde element wordt in dit lege slot toegevoegd. Vervolgens wordt dit element vergeleken met de onderliggende knooppunten, dat wil zeggen het linkerkind en het rechterkind, en verwisseld met de kleinste van de twee. Het blijft langs de boom naar beneden bewegen totdat de heap-eigenschap is hersteld.
Toepassingen van prioriteitswachtrij
Hieronder volgen de toepassingen van de prioriteitswachtrij:
- Het wordt gebruikt in het kortste pad-algoritme van Dijkstra.
- Het wordt gebruikt in het algoritme van prim
- Het wordt gebruikt in datacompressietechnieken zoals Huffman-code.
- Het wordt gebruikt in heap-sortering.
- Het wordt ook gebruikt in besturingssystemen zoals prioriteitsplanning, taakverdeling en interruptafhandeling.
Programma om de prioriteitswachtrij te maken met behulp van de binaire max-heap.
#include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i > 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong> </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>