I denna handledning lär du dig vilken prioritetskö som är. Du kommer också att lära dig om dess implementeringar i Python, Java, C och C ++.
En prioritetskö är en speciell typ av kö där varje element är associerat med en prioritet och serveras enligt dess prioritet. Om element med samma prioritet förekommer serveras de enligt deras ordning i kön.
Generellt betraktas själva elementets värde för att tilldela prioriteten.
Till exempel betraktas elementet med det högsta värdet som det högsta prioritetselementet. I andra fall kan vi dock anta att elementet med det lägsta värdet är det högsta prioritetselementet. I andra fall kan vi ställa in prioriteringar efter våra behov.
Ta bort element med högsta prioritet
Skillnad mellan Priority Queue och Normal Queue
I en kö implementeras först-in-först-ut-regeln, medan värdena i en prioritetskö tas bort på grundval av prioritet . Elementet med högsta prioritet tas bort först.
Implementering av prioritetskö
Prioritetskön kan implementeras med hjälp av en matris, en länkad lista, en högdata-struktur eller ett binärt sökträd. Bland dessa datastrukturer ger heapdatastrukturen ett effektivt genomförande av prioritetsköer.
Därför kommer vi att använda heap-datastrukturen för att implementera prioritetskön i denna handledning. En max-heap implementeras i följande operationer. Om du vill lära dig mer om det, besök max-heap och mean-heap.
En jämförande analys av olika implementeringar av prioritetskön ges nedan.
| Operationer | titt | Föra in | radera |
|---|---|---|---|
| Länkad lista | O(1) | O(n) | O(1) |
| Binär hög | O(1) | O(log n) | O(log n) |
| Binärt sökträd | O(1) | O(log n) | O(log n) |
Prioriterad köoperation
Grundläggande funktioner i en prioritetskö är att infoga, ta bort och kika in element.
Innan du studerar prioritetskön, se heapdatastrukturen för en bättre förståelse av binär heap eftersom den används för att implementera prioritetskön i den här artikeln.
1. Infoga ett element i prioritetskön
Att infoga ett element i en prioritetskö (max-heap) görs enligt följande steg.
- Sätt in det nya elementet i slutet av trädet.
Infoga ett element i slutet av kön - Heapify trädet.
Heapify efter införande
Algoritm för infogning av ett element i prioritetskön (max-heap)
Om det inte finns någon nod skapar du en newNode. annars (en nod finns redan) infoga newNoden i slutet (sista noden från vänster till höger.) heapify arrayen
För Min Heap modifieras ovanstående algoritm så att den parentNodealltid är mindre än newNode.
2. Ta bort ett element från prioritetskön
Radering av ett element från en prioritetskö (max-heap) görs enligt följande:
- Välj det element som ska raderas.
Välj det element som ska raderas - Byt det med det sista elementet.
Byt med det sista bladnodselementet - Ta bort det sista elementet.
Ta bort det sista elementbladet - Heapify trädet.
Heapify prioritetskön
Algoritm för radering av ett element i prioritetskön (max-heap)
Om nodeToBeDeleted är leafNode ta bort noden Else swap nodeToBeDeleted med lastLeafNode ta bort noteToBeDeleted heapify arrayen
För Min Heap modifieras ovanstående algoritm så att båda childNodesär mindre än currentNode.
3. Kikar från prioritetskön (Hitta max / min)
Peek-operationen returnerar det maximala elementet från Max Heap eller minimi-elementet från Min Heap utan att noden raderas.
För både Max heap och Min Heap
returnera rootNode
4. Extrahera max / min från prioritetskön
Extract-Max returnerar noden med maximalt värde efter att ha tagit bort den från en Max Heap medan Extract-Min returnerar noden med minsta värde efter att ha tagit bort den från Min Heap.
Prioriteringsköimplementeringar i Python, Java, C och 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öapplikationer
Några av applikationerna i en prioritetskö är:
- Dijkstras algoritm
- för att implementera stack
- för lastbalansering och avbrytande av hantering i ett operativsystem
- för datakomprimering i Huffman-kod
