Ebben az oktatóanyagban megtudhatja, mi az elsőbbségi sor. Ezenkívül megismerheti Python, Java, C és C ++ implementációit.
A prioritási várólista egy speciális sorsor, amelyben minden elem társul egy prioritással, és prioritása szerint kerül kiszolgálásra. Ha azonos prioritású elemek fordulnak elő, akkor a sorrendjük szerint kerülnek kiszolgálásra a sorban.
Általában maga az elem értéke veszi figyelembe a prioritás hozzárendelését.
Például a legmagasabb értékű elemet tekintjük a legmagasabb prioritású elemnek. Más esetekben azonban a legkisebb értékű elemet feltételezhetjük a legmagasabb prioritású elemként. Más esetekben szükségleteinknek megfelelően állíthatunk prioritásokat.
A legmagasabb prioritású elem eltávolítása
Különbség a prioritási és a normál várakozási sor között
Sorban az első az elsőben ki szabályt hajtják végre, míg egy prioritási sorban az értékeket a prioritás alapján távolítják el . Először a legmagasabb prioritású elem kerül eltávolításra.
A prioritási sor megvalósítása
A prioritási sor egy tömb, egy összekapcsolt lista, egy halom adatszerkezet vagy egy bináris keresési fa segítségével valósítható meg. Ezen adatstruktúrák közül a halom adatstruktúra biztosítja a prioritási sorok hatékony megvalósítását.
Ezért a halom adatstruktúrát fogjuk használni az oktatóanyag prioritási sorának megvalósításához. A következő műveletekben egy maximális kupac van. Ha többet szeretne megtudni róla, kérjük, látogasson el a max-heap és a mean-heap oldalra.
Az alábbiakban összehasonlító elemzést adunk a prioritási sor különböző megvalósításairól.
| Tevékenységek | kandikál | betét | töröl |
|---|---|---|---|
| Összekapcsolt lista | O(1) | O(n) | O(1) |
| Bináris kupac | O(1) | O(log n) | O(log n) |
| Bináris keresési fa | O(1) | O(log n) | O(log n) |
Kiemelt várólista műveletek
A prioritási sor alapvető műveletei az elemek beszúrása, eltávolítása és bepillantása.
Mielőtt tanulmányozná a prioritási várólistát, kérjük, olvassa el a halom adatszerkezetét a bináris halom jobb megértése érdekében, mivel az a cikk elsőbbségi sorának megvalósítására szolgál.
1. Helyezzen be egy elemet a Prioritási sorba
Elem beszúrása egy prioritási sorba (max-halom) a következő lépésekkel történik.
- Helyezze be az új elemet a fa végébe.
Helyezzen be egy elemet a sor végére - Halmozd fel a fát.
Beszúrás után halmozzuk fel
Algoritmus egy elem beillesztésére a prioritási sorba (max-halom)
Ha nincs csomópont, hozzon létre egy új csomópontot. másképp (egy csomópont már van) illessze be az újNode-ot a végére (az utolsó csomópont balról jobbra.) Heapify a tömb
Min Heap esetében a fenti algoritmus úgy módosul, hogy parentNodemindig kisebb legyen, mint newNode.
2. Elem törlése a Prioritási sorból
Egy elem törlése a prioritási sorból (max-halom) a következőképpen történik:
- Válassza ki a törölni kívánt elemet.
Válassza ki a törölni kívánt elemet - Cserélje az utolsó elemre.
Cserélje az utolsó levélcsomópont-elemre - Távolítsa el az utolsó elemet.
Távolítsa el az utolsó elemlevelet - Halmozd fel a fát.
Fejlessze a prioritási sort
Algoritmus egy elem törléséhez a prioritási sorban (max-halom)
Ha a nodeToBeDeleted a leafNode, távolítsa el a csomópontot Else swap csomópontot
Min Heap esetében a fenti algoritmust úgy módosítják, hogy mindkettő childNodeskisebb legyen, mint currentNode.
3. Pillantás a prioritási sorból (max / perc keresése)
A peek művelet a csomópont törlése nélkül adja vissza a maximális elemet a Max Heap-ból, a minimális elemet pedig a Min Heap-ből.
Mind Max halomhoz, mind Min Halomhoz
return rootNode
4. Extract-Max / Min a prioritási sorból
Az Extract-Max a maximális értékű csomópontot adja vissza, miután eltávolította a Max Heap-ból, míg az Extract-Min a minimális értékkel visszaadja a csomópontot, miután eltávolította a Min Heap-ból.
Prioritási várólista megvalósítások Pythonban, Java-ban, C-ben és C ++ -on
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); )
Kiemelt várólista alkalmazások
Néhány prioritási sor alkalmazás a következő:
- Dijkstra algoritmusa
- verem megvalósításához
- a terhelés kiegyenlítésére és az operációs rendszer megszakításainak kezelésére
- az adatok tömörítéséhez Huffman-kódban
