I denne opplæringen lærer du hva prioritetskø er. Du vil også lære om implementeringene i Python, Java, C og C ++.
En prioritetskø er en spesiell type kø der hvert element er tilknyttet en prioritet og serveres i henhold til dets prioritet. Hvis elementer med samme prioritet forekommer, blir de servert i henhold til deres rekkefølge i køen.
Generelt vurderes verdien av selve elementet for å tildele prioriteten.
For eksempel blir elementet med høyest verdi betraktet som det høyeste prioritetselementet. I andre tilfeller kan vi imidlertid anta elementet med den laveste verdien som det høyeste prioritetselementet. I andre tilfeller kan vi sette prioriteringer i henhold til våre behov.
Fjerner elementet med høyest prioritet
Forskjellen mellom prioritetskø og normal kø
I en kø implementeres først-inn-først-ut-regelen, mens verdiene i en prioritetskø fjernes på grunnlag av prioritet . Elementet med høyest prioritet fjernes først.
Implementering av Priority Queue
Prioritetskø kan implementeres ved hjelp av en matrise, en koblet liste, en haugdatastruktur eller et binært søketre. Blant disse datastrukturene gir heap-datastruktur en effektiv implementering av prioritetskøer.
Derfor vil vi bruke heap-datastrukturen til å implementere prioritetskøen i denne opplæringen. En maks-heap er implementert i følgende operasjoner. Hvis du vil lære mer om det, kan du gå til max-heap og mean-heap.
En komparativ analyse av forskjellige implementeringer av prioritetskø er gitt nedenfor.
| Operasjoner | kikke | sett inn | slett |
|---|---|---|---|
| Koblet liste | O(1) | O(n) | O(1) |
| Binær haug | O(1) | O(log n) | O(log n) |
| Binært søketre | O(1) | O(log n) | O(log n) |
Prioritetskøoperasjoner
Grunnleggende operasjoner i en prioritetskø er å sette inn, fjerne og kikke på elementer.
Før du studerer prioritetskøen, kan du referere til haupdatastrukturen for å få en bedre forståelse av binær heap da den brukes til å implementere prioritetskøen i denne artikkelen.
1. Sette inn et element i prioritetskøen
Å sette inn et element i en prioritetskø (max-heap) gjøres ved å følge trinnene nedenfor.
- Sett inn det nye elementet på slutten av treet.
Sett inn et element på slutten av køen - Høvle treet.
Heapify etter innsetting
Algoritme for innsetting av et element i prioritetskø (max-heap)
Hvis det ikke er noen node, oppretter du en newNode. annet (en node er allerede til stede) sett inn newNode på slutten (siste node fra venstre til høyre.) heapify array
For Min Heap blir algoritmen ovenfor modifisert slik at den parentNodealltid er mindre enn newNode.
2. Slette et element fra prioritetskøen
Slette et element fra en prioritetskø (max-heap) gjøres som følger:
- Velg elementet som skal slettes.
Velg elementet som skal slettes - Bytt den med det siste elementet.
Bytt med det siste bladknutepunktelementet - Fjern det siste elementet.
Fjern det siste elementbladet - Høvle treet.
Heapify prioritetskøen
Algoritme for sletting av et element i prioritetskøen (max-heap)
Hvis nodeToBeDeleted er leafNode fjern noden Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify array
For Min Heap blir algoritmen ovenfor modifisert slik at begge childNodeser mindre enn currentNode.
3. Titter fra Priority Queue (Finn maks / min)
Tittoperasjon returnerer maksimalt element fra Max Heap eller minimum element fra Min Heap uten å slette noden.
For både Max heap og Min Heap
return rootNode
4. Trekk ut maks / min fra prioritetskøen
Extract-Max returnerer noden med maksimal verdi etter at den er fjernet fra en Max Heap, mens Extract-Min returnerer noden med minimumsverdien etter at den er fjernet fra Min Heap.
Prioriteringskøimplementeringer i Python, Java, C og C ++
Python Java C C ++ # Priority Queue implementation in Python # Function to heapify the tree def heapify(arr, n, i): # Find the largest among root, left child and right child largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r # Swap and continue heapifying if root is not largest if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) # Function to insert an element into the tree def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum) for i in range((size // 2) - 1, -1, -1): heapify(array, size, i) # Function to delete an element from the tree def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size - 1) = array(size - 1), array(i) array.remove(size - 1) for i in range((len(array) // 2) - 1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))
// Priority Queue implementation in Java import java.util.ArrayList; class Heap ( // Function to heapify the tree void heapify(ArrayList hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(ArrayList hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.add(newNum); ) else ( hT.add(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(ArrayList hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; j--) ( heapify(hT, j); ) ) // Print the tree void printArray(ArrayList array, int size) ( for (Integer i : array) ( System.out.print(i + " "); ) System.out.println(); ) // Driver code public static void main(String args()) ( ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println("Max-Heap array: "); h.printArray(array, size); h.deleteNode(array, 4); System.out.println("After deleting an element: "); h.printArray(array, size); ) )
// Priority Queue implementation in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) // Function to insert an element into the tree void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) // Function to delete an element from the tree void deleteRoot(int array(), int num) ( int i; for (i = 0; i = 0; i--) ( heapify(array, size, i); ) ) // Print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) // Driver code int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )
// Priority Queue implementation in C++ #include #include using namespace std; // Function to swap position of two elements void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) // Function to heapify the tree void heapify(vector &hT, int i) ( int size = hT.size(); // Find the largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) // Function to insert an element into the tree void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) // Function to delete an element from the tree void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i = 0; i--) ( heapify(hT, i); ) ) // Print the tree void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) // Driver code int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )
Prioritetskø-applikasjoner
Noen av programmene i en prioritetskø er:
- Dijkstras algoritme
- for implementering av stack
- for lastbalansering og avbruddshåndtering i et operativsystem
- for datakomprimering i Huffman-kode
