În acest tutorial, veți afla ce este coada prioritară. De asemenea, veți afla despre implementările sale în Python, Java, C și C ++.
O coadă de prioritate este un tip special de coadă în care fiecare element este asociat cu o prioritate și este servit în funcție de prioritatea sa. Dacă apar elemente cu aceeași prioritate, acestea sunt servite conform ordinii lor în coadă.
În general, valoarea elementului în sine este luată în considerare pentru atribuirea priorității.
De exemplu, elementul cu cea mai mare valoare este considerat elementul cu cea mai mare prioritate. Cu toate acestea, în alte cazuri, putem presupune elementul cu cea mai mică valoare ca element cu cea mai mare prioritate. În alte cazuri, putem stabili priorități în funcție de nevoile noastre.
Eliminarea elementului cu cea mai mare prioritate
Diferența dintre coada prioritară și coada normală
Într-o coadă, se implementează regula first-in-first-out , în timp ce, într-o coadă prioritară, valorile sunt eliminate pe baza priorității . Elementul cu cea mai mare prioritate este eliminat mai întâi.
Implementarea cozii prioritare
Coada prioritară poate fi implementată utilizând o matrice, o listă legată, o structură de date heap sau un arbore de căutare binară. Printre aceste structuri de date, structura de date heap oferă o implementare eficientă a cozilor prioritare.
Prin urmare, vom folosi structura de date heap pentru a implementa coada prioritară în acest tutorial. Un maxim-heap este implementat în următoarele operațiuni. Dacă doriți să aflați mai multe despre aceasta, vă rugăm să vizitați max-heap și mean-heap.
O analiză comparativă a diferitelor implementări ale cozii prioritare este dată mai jos.
| Operațiuni | arunca o privire | introduce | șterge |
|---|---|---|---|
| Listă legată | O(1) | O(n) | O(1) |
| Heap binar | O(1) | O(log n) | O(log n) |
| Arborele de căutare binar | O(1) | O(log n) | O(log n) |
Operații de coadă prioritară
Operațiile de bază ale unei cozi prioritare sunt inserarea, eliminarea și vizualizarea elementelor.
Înainte de a studia coada prioritară, vă rugăm să consultați structura de date a heap-ului pentru o mai bună înțelegere a heap-ului binar, deoarece este utilizată pentru a implementa coada prioritară în acest articol.
1. Introducerea unui element în coada prioritară
Inserarea unui element într-o coadă prioritară (max-heap) se face prin următorii pași.
- Introduceți noul element la capătul arborelui.
Introduceți un element la sfârșitul cozii - Heapify copac.
Heapify după inserare
Algoritm pentru inserarea unui element în coada de prioritate (max-heap)
Dacă nu există nod, creați un nou nod. altfel (un nod este deja prezent) introduceți noul nod la sfârșit (ultimul nod de la stânga la dreapta.) heapify array
Pentru Min Heap, algoritmul de mai sus este modificat astfel încât să parentNodefie întotdeauna mai mic decât newNode.
2. Ștergerea unui element din coada prioritară
Ștergerea unui element dintr-o coadă de prioritate (max-heap) se face după cum urmează:
- Selectați elementul de șters.
Selectați elementul de șters - Schimbați-l cu ultimul element.
Schimbați cu ultimul element de nod frunză - Eliminați ultimul element.
Îndepărtați ultima frunză de element - Heapify copac.
Heapify coada de prioritate
Algoritm pentru ștergerea unui element din coada de prioritate (max-heap)
Dacă nodeToBeDeleted este leafNode eliminați nodul Else swap nodeToBeDeleted cu lastLeafNode eliminați noteToBeDeleted heapify array
Pentru Min Heap, algoritmul de mai sus este modificat astfel încât ambele să childNodesfie mai mici decât currentNode.
3. Privirea din coada prioritară (Găsiți max / min)
Operația Peek returnează elementul maxim din Max Heap sau elementul minim din Min Heap fără a șterge nodul.
Atât pentru Max heap, cât și pentru Min Heap
returnează rootNode
4. Extract-Max / Min din coada prioritară
Extract-Max returnează nodul cu valoare maximă după ce îl scoate dintr-un Heap Max, în timp ce Extract-Min returnează nodul cu valoare minimă după eliminarea acestuia din Min Heap.
Implementări coadă prioritară în Python, Java, C și 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); )
Aplicații coadă prioritară
Unele dintre aplicațiile unei cozi prioritare sunt:
- Algoritmul lui Dijkstra
- pentru implementarea stivei
- pentru echilibrarea sarcinii și manipularea întreruperilor într-un sistem de operare
- pentru compresia datelor în codul Huffman
