I denne vejledning lærer du, hvad prioritetskø er. Du vil også lære om dets implementeringer i Python, Java, C og C ++.
En prioritetskø er en særlig køtype, hvor hvert element er knyttet til en prioritet og serveres i henhold til dets prioritet. Hvis der opstår elementer med samme prioritet, serveres de efter deres rækkefølge i køen.
Generelt betragtes værdien af selve elementet for at tildele prioriteten.
For eksempel betragtes elementet med den højeste værdi som det højeste prioritetselement. I andre tilfælde kan vi dog antage, at elementet med den laveste værdi er det højeste prioritetselement. I andre tilfælde kan vi sætte prioriteter efter vores behov.
Fjernelse af element med højeste prioritet
Forskel mellem prioritetskø og normal kø
I en kø implementeres først-i-første-ud-reglen, mens værdierne i en prioritetskø fjernes på basis af prioritet . Elementet med den højeste prioritet fjernes først.
Implementering af prioritetskø
Prioritetskø kan implementeres ved hjælp af en matrix, en sammenkædet liste, en bunke-datastruktur eller et binært søgetræ. Blandt disse datastrukturer giver heap-datastruktur en effektiv implementering af prioritetskøer.
Derfor bruger vi heap-datastrukturen til at implementere prioritetskøen i denne vejledning. En max-heap implementeres i følgende operationer. Hvis du vil lære mere om det, kan du besøge max-heap og mean-heap.
En komparativ analyse af forskellige implementeringer af prioritetskø er givet nedenfor.
| Operationer | kigge | indsæt | slet |
|---|---|---|---|
| Tilknyttet liste | O(1) | O(n) | O(1) |
| Binær bunke | O(1) | O(log n) | O(log n) |
| Binært søgetræ | O(1) | O(log n) | O(log n) |
Prioriterede køoperationer
Grundlæggende operationer i en prioritetskø indsætter, fjerner og kigger på elementer.
Inden du studerer prioritetskøen, henvises til beap-datastrukturen for en bedre forståelse af binær heap, da den bruges til at implementere prioritetskøen i denne artikel.
1. Indsættelse af et element i prioritetskøen
Indsættelse af et element i en prioritetskø (max-heap) udføres ved hjælp af følgende trin.
- Indsæt det nye element i slutningen af træet.
Indsæt et element i slutningen af køen - Hæv træet.
Heapify efter indsættelse
Algoritme til indsættelse af et element i prioritetskø (max-heap)
Hvis der ikke er nogen node, skal du oprette en newNode. ellers (en knude er allerede til stede) indsæt newNode i slutningen (sidste knude fra venstre mod højre.) heapify arrayet
For Min Heap ændres ovenstående algoritme, så den parentNodealtid er mindre end newNode.
2. Sletning af et element fra prioritetskøen
Sletning af et element fra en prioritetskø (max-heap) gøres som følger:
- Vælg det element, der skal slettes.
Vælg det element, der skal slettes - Skift det med det sidste element.
Byt med det sidste bladknudepunktelement - Fjern det sidste element.
Fjern det sidste elementblad - Hæv træet.
Heapify prioritetskøen
Algoritme til sletning af et element i prioritetskøen (max-heap)
Hvis nodeToBeDeleted er leafNode fjern noden Else swap nodeToBeDeleted med lastLeafNode fjern noteToBeDeleted heapify arrayet
For Min Heap ændres ovenstående algoritme, så begge childNodeser mindre end currentNode.
3. Kigger fra prioritetskøen (Find maks / min)
Peek-operation returnerer det maksimale element fra Max Heap eller minimum element fra Min Heap uden at slette noden.
For både Max bunke og Min bunke
returner rootNode
4. Uddrag maks / min fra prioritetskøen
Extract-Max returnerer noden med maksimal værdi efter at have fjernet den fra en Max Heap, mens Extract-Min returnerer noden med minimumsværdien efter at have fjernet den fra Min Heap.
Prioriterede kø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); )
Prioriterede køapplikationer
Nogle af applikationerne i en prioritetskø er:
- Dijkstras algoritme
- til implementering af stack
- til belastningsbalancering og afbrydelse af håndtering i et operativsystem
- til datakomprimering i Huffman-kode
