Tässä opetusohjelmassa opit, mikä prioriteettijono on. Opit myös sen toteutuksista Pythonissa, Java: ssa, C: ssä ja C ++: ssa.
Prioriteettijono on erityinen jonotyyppi, jossa jokainen elementti liittyy prioriteettiin ja sitä palvellaan prioriteetin mukaan. Jos elementtejä, joilla on sama prioriteetti, esiintyy, ne näytetään jonossa olevan järjestyksen mukaan.
Yleensä prioriteetin määrittämisessä otetaan huomioon itse elementin arvo.
Esimerkiksi korkeimman arvon elementtiä pidetään tärkeimpänä prioriteettina. Muissa tapauksissa voimme kuitenkin olettaa, että alimman arvon omaava elementti on korkeimman prioriteetin elementti. Muissa tapauksissa voimme asettaa prioriteetit tarpeidemme mukaan.
Korkeimman prioriteetin elementin poistaminen
Ero tärkeysjärjestyksen ja normaalin jonon välillä
Jonossa toteutetaan ensin ensin sisään-ulos -sääntö, kun taas prioriteettijonossa arvot poistetaan prioriteetin perusteella . Korkeimman prioriteetin elementti poistetaan ensin.
Prioriteettijonon toteutus
Prioriteettijono voidaan toteuttaa käyttämällä taulukkoa, linkitettyä luetteloa, kasan tietorakennetta tai binaarista hakupuuta. Näistä tietorakenteista kasan tietorakenne tarjoaa tehokkaan prioriteettijonojen toteuttamisen.
Siksi käytämme kasan tietorakennetta prioriteettijonon toteuttamiseen tässä opetusohjelmassa. Suurin kasa on kone on seuraavissa toiminnoissa. Jos haluat oppia lisää siitä, käy osoitteessa max-heap ja mean-heap.
Seuraavassa esitetään vertaileva analyysi prioriteettijonon eri toteutuksista.
| Toiminnot | kurkistaa | lisää | poistaa |
|---|---|---|---|
| Linkitetty luettelo | O(1) | O(n) | O(1) |
| Binaarinen kasa | O(1) | O(log n) | O(log n) |
| Binaarinen hakupuu | O(1) | O(log n) | O(log n) |
Prioriteettijonotoiminnot
Prioriteettijonon perustoiminnot ovat elementtien lisääminen, poistaminen ja kurkistaminen.
Ennen kuin tarkastelet prioriteettijonoa, tutustu kasan tietorakenteeseen saadaksesi paremman käsityksen binäärikoneesta, koska sitä käytetään tämän artiklan prioriteettijonon toteuttamiseen.
1. Lisää elementti prioriteettijonoon
Elementin lisääminen prioriteettijonoon (max-kasa) tapahtuu seuraavasti.
- Lisää uusi elementti puun päähän.
Lisää elementti jonon loppuun - Kasvata puuta.
Kasaa lisäyksen jälkeen
Algoritmi elementin lisäämiseksi prioriteettijonoon (max-kasa)
Jos solmua ei ole, luo uusi solmu. muuten (solmu on jo läsnä) lisää uusi solmu loppuun (viimeinen solmu vasemmalta oikealle.) kasaa taulukko
Min Heapia varten yllä olevaa algoritmia muokataan siten, että se parentNodeon aina pienempi kuin newNode.
2. Elementin poistaminen prioriteettijonosta
Elementin poistaminen prioriteettijonosta (max-heap) tapahtuu seuraavasti:
- Valitse poistettava elementti.
Valitse poistettava elementti - Vaihda se viimeisen elementin kanssa.
Vaihda viimeisen lehtisolmuelementin kanssa - Poista viimeinen elementti.
Poista viimeinen elementtilehti - Kasvata puuta.
Heapify prioriteettijono
Algoritmi elementin poistamiseksi prioriteettijonosta (max-kasa)
Jos nodeToBeDeleted on leafNode, poista solmu Muuten vaihda nodeToBeDeleted with lastLeafNode poista noteToBeDeleted heapify array
Min Heapia varten yllä olevaa algoritmia muokataan niin, että molemmat childNodesovat pienempiä kuin currentNode.
3. Kurkistus prioriteettijonolta (Etsi maksimi / min)
Peek-toiminto palauttaa enimmäiselementin Max Heapista tai minimielementin Min Heapista poistamatta solmua.
Sekä Max-kasalle että Min-kasalle
palauta rootNode
4. Extract-Max / Min prioriteettijonosta
Extract-Max palauttaa solmun suurimmalla arvolla sen jälkeen, kun se on poistettu Max-kasasta, kun taas Extract-Min palauttaa solmun vähimmäisarvolla, kun se on poistettu Min-kasasta.
Prioriteettijonon toteutukset Pythonissa, Java: ssa, C: ssä ja C ++: ssa
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); )
Prioriteettijonosovellukset
Jotkut prioriteettijonon sovelluksista ovat:
- Dijkstran algoritmi
- pinon toteuttamiseen
- kuormituksen tasapainottamiseen ja keskeytysten käsittelyyn käyttöjärjestelmässä
- tietojen pakkaamiseen Huffman-koodissa
