Šajā apmācībā jūs uzzināsiet, kāda ir prioritārā rinda. Jūs arī uzzināsiet par tā ieviešanu Python, Java, C un C ++.
Prioritārā rinda ir īpašs rindas veids, kurā katrs elements ir saistīts ar prioritāti un tiek apkalpots atbilstoši tā prioritātei. Ja rodas elementi ar tādu pašu prioritāti, tie tiek apkalpoti atbilstoši to secībai rindā.
Parasti prioritātes piešķiršanai tiek ņemta vērā paša elementa vērtība.
Piemēram, elements ar visaugstāko vērtību tiek uzskatīts par augstākās prioritātes elementu. Tomēr citos gadījumos mēs varam pieņemt elementu ar zemāko vērtību kā augstākās prioritātes elementu. Citos gadījumos mēs varam noteikt prioritātes atbilstoši savām vajadzībām.
Augstākās prioritātes elementa noņemšana
Atšķirība starp prioritāro rindu un parasto rindu
Rindā tiek ieviests noteikums “ pirmais iekšā pirmais”, turpretī prioritārajā rindā vērtības tiek noņemtas , pamatojoties uz prioritāti . Vispirms tiek noņemts elements ar augstāko prioritāti.
Prioritārās rindas ieviešana
Prioritāro rindu var ieviest, izmantojot masīvu, saistītu sarakstu, kaudzes datu struktūru vai bināru meklēšanas koku. Starp šīm datu struktūrām kaudzes datu struktūra nodrošina efektīvu prioritāro rindu ieviešanu.
Tādējādi mēs izmantosim kaudzes datu struktūru, lai šajā apmācībā ieviestu prioritāro rindu. Maksimālais kaudze ir mašīna šādās darbībās. Ja vēlaties uzzināt vairāk par to, lūdzu, apmeklējiet max-heap un mean-heap.
Zemāk sniegta dažādu prioritārās rindas ieviešanas gadījumu salīdzinošā analīze.
| Operācijas | palūrēt | ievietot | dzēst |
|---|---|---|---|
| Saistītais saraksts | O(1) | O(n) | O(1) |
| Binārais kaudze | O(1) | O(log n) | O(log n) |
| Binārais meklēšanas koks | O(1) | O(log n) | O(log n) |
Prioritārās rindas darbības
Prioritārās rindas pamatdarbības ir elementu ievietošana, noņemšana un palūrēšana.
Pirms izpētīt prioritāro rindu, lūdzu, skatiet kaudzes datu struktūru, lai labāk izprastu bināro kaudzi, jo tā tiek izmantota prioritārā rindas ieviešanai šajā rakstā.
1. Elementa ievietošana prioritārajā rindā
Elementa ievietošana prioritārajā rindā (max-heap) tiek veikta, veicot šādas darbības.
- Ievietojiet jauno elementu koka galā.
Ievietojiet elementu rindas beigās - Uzkrājiet koku.
Pēc ievietošanas palieliniet
Algoritms elementa ievietošanai prioritārajā rindā (max-kaudze)
Ja mezgla nav, izveidojiet jaunu mezglu. cits (mezgls jau ir) ievietojiet newNode beigās (pēdējais mezgls no kreisās uz labo.) Heapify masīvs
Min Heap gadījumā iepriekšminētais algoritms tiek modificēts tā, lai parentNodetas vienmēr būtu mazāks par newNode.
2. Elementa dzēšana no prioritātes rindas
Elementa dzēšana no prioritārās rindas (max-heap) tiek veikta šādi:
- Atlasiet dzēšamo elementu.
Atlasiet dzēšamo elementu - Apmainiet to ar pēdējo elementu.
Apmainiet ar pēdējo lapu mezgla elementu - Noņemiet pēdējo elementu.
Noņemiet pēdējo elementa lapu - Uzkrājiet koku.
Papildiniet prioritātes rindu
Algoritms elementa dzēšanai prioritārajā rindā (max-kaudze)
Ja nodeToBeDeleted ir leafNode, noņemiet mezglu Else swap mezgluToBeDeleted ar lastLeafNode noņemt noteToBeDeleted palieliniet masīvu
Min Heapam iepriekšminētais algoritms tiek modificēts tā, lai abi childNodesbūtu mazāki par currentNode.
3. Skatīšanās no prioritātes rindas (atrast maks. / Min)
Peek darbība atgriež maksimālo elementu no Max Heap vai minimālo elementu no Min Heap, neizdzēšot mezglu.
Gan Max kaudzei, gan Min Heap
atgriezt rootNode
4. Extract-Max / Min no prioritātes rindas
Extract-Max atgriež mezglu ar maksimālo vērtību pēc tā noņemšanas no Max Heap, savukārt Extract-Min atgriež mezglu ar minimālo vērtību pēc tā noņemšanas no Min Heap.
Prioritārās rindas ieviešana Python, Java, C un 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); )
Prioritārās rindas pieteikumi
Daži no prioritārās rindas lietojumiem ir:
- Dijkstra algoritms
- kaudzes ieviešanai
- slodzes līdzsvarošanai un pārtraukumu apstrādei operētājsistēmā
- datu saspiešanai Huffman kodā
