V tej vadnici boste izvedeli, kaj je prednostna vrsta. Spoznali boste tudi njegove izvedbe v Pythonu, Javi, C in C ++.
Prioritetna vrsta je posebna vrsta čakalne vrste, v kateri je vsak element povezan s prednostjo in je vročen v skladu s svojo prioriteto. Če se pojavijo elementi z enako prednostjo, so v čakalni vrsti vročeni po njihovem vrstnem redu.
Na splošno velja, da je za določanje prioritete upoštevana vrednost samega elementa.
Na primer, element z najvišjo vrednostjo se šteje za element z najvišjo prioriteto. V drugih primerih pa lahko element z najnižjo vrednost predpostavimo kot element z najvišjo prioriteto. V drugih primerih lahko prednostne naloge določimo glede na svoje potrebe.
Odstranjevanje najvišje prioritetnega elementa
Razlika med prednostno in običajno vrsto
V čakalni vrsti se izvede pravilo prvi v prvem, medtem ko se v čakalni vrsti prednostne vrednosti odstranijo na podlagi prioritete . Najprej se odstrani element z najvišjo prioriteto.
Izvajanje prioritetne čakalne vrste
Prednostno čakalno vrsto je mogoče izvesti z uporabo polja, povezanega seznama, podatkovne strukture kopice ali binarnega drevesa iskanja. Med temi podatkovnimi strukturami struktura podatkov kopice omogoča učinkovito izvajanje prednostnih čakalnih vrst.
Zato bomo za uporabo prednostne čakalne vrste v tej vadnici uporabili strukturo podatkov kopice. Max-heap je izveden v naslednjih operacijah. Če želite izvedeti več o tem, obiščite max-heap in mean-heap.
Spodaj je podana primerjalna analiza različnih izvedb prednostne čakalne vrste.
| Operacije | pokukati | vstavi | izbriši |
|---|---|---|---|
| Povezani seznam | O(1) | O(n) | O(1) |
| Binarni kup | O(1) | O(log n) | O(log n) |
| Binarno drevo iskanja | O(1) | O(log n) | O(log n) |
Prednostne operacije v čakalni vrsti
Osnovne operacije prednostne čakalne vrste so vstavljanje, odstranjevanje in pokukanje elementov.
Preden preučite prednostno vrsto, si oglejte strukturo podatkov kopice za boljše razumevanje binarne kopice, saj se uporablja za izvajanje prednostne čakalne vrste v tem članku.
1. Vstavljanje elementa v prednostno vrsto
Vstavljanje elementa v prednostno čakalno vrsto (max-heap) se izvede z naslednjimi koraki.
- Na koncu drevesa vstavite nov element.
Vstavite element na konec čakalne vrste - Onesnaži drevo.
Po vstavitvi oživite
Algoritem za vstavljanje elementa v prednostno vrsto (max-heap)
Če vozlišča ni, ustvarite novo vozlišče. sicer (vozlišče je že prisotno) vstavite newNode na koncu (zadnje vozlišče od leve proti desni).
Za Min Heap je zgornji algoritem spremenjen tako, da parentNodeje vedno manjši od newNode.
2. Brisanje elementa iz prioritetne čakalne vrste
Brisanje elementa iz prednostne čakalne vrste (max-heap) se izvede na naslednji način:
- Izberite element, ki ga želite izbrisati.
Izberite element, ki ga želite izbrisati - Zamenjajte ga z zadnjim elementom.
Zamenjajte z zadnjim elementom vozlišča listov - Odstranite zadnji element.
Odstranite zadnji listni element - Onesnaži drevo.
Omogočite prednostno vrsto
Algoritem za brisanje elementa v prednostni vrsti (max-heap)
Če je nodeToBeDeleted leafNode, odstranite vozlišče Sicer zamenjajte nodeToBeDeleted z lastLeafNode odstranite noteToBeDeleted, da se matrificira matrika
Za Min Heap je zgornji algoritem spremenjen tako, da sta oba childNodesmanjša od currentNode.
3. Pogled iz prioritetne čakalne vrste (Najdi maks. / Min.)
Operacija Peek vrne največ element iz Max Heap ali najmanjši element iz Min Heap brez brisanja vozlišča.
Tako za Max heap kot za Min Heap
vrni rootNode
4. Izvleček največ / min iz prioritetne čakalne vrste
Extract-Max vrne vozlišče z največjo vrednostjo, potem ko ga odstrani iz Max Heap, medtem ko Extract-Min vrne vozlišče z minimalno vrednostjo, potem ko ga odstrani iz Min Heap.
Izvedbe prioritetne vrste v Pythonu, Javi, C in 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); )
Prednostne aplikacije v čakalni vrsti
Nekatere aplikacije prednostne čakalne vrste so:
- Dijkstrin algoritem
- za izvedbo sklada
- za uravnoteženje obremenitve in obdelavo prekinitev v operacijskem sistemu
- za stiskanje podatkov v Huffmanovi kodi
