Šioje pamokoje sužinosite, kokia yra prioritetinė eilė. Be to, sužinosite apie jo įgyvendinimą „Python“, „Java“, C ir C ++.
Prioritetinė eilė yra specialus eilės tipas, kai kiekvienas elementas yra susietas su prioritetu ir aptarnaujamas pagal jo prioritetą. Jei atsiranda to paties prioriteto elementai, jie pateikiami pagal eilės eilės tvarką.
Paprastai priskiriant prioritetą atsižvelgiama į paties elemento vertę.
Pavyzdžiui, elementas, kurio vertė didžiausia, laikomas aukščiausio prioriteto elementu. Tačiau kitais atvejais aukščiausio prioriteto elementu galime laikyti elementą, kurio vertė mažiausia. Kitais atvejais galime nustatyti prioritetus pagal savo poreikius.
Aukščiausio prioriteto elemento pašalinimas
Skirtumas tarp prioritetinės eilės ir įprastos eilės
Eilėje įgyvendinama taisyklė „pirmas į pirmą“ , o prioritetinėje eilėje reikšmės pašalinamos pagal prioritetą . Pirmiausia pašalinamas elementas, turintis aukščiausią prioritetą.
Prioritetinės eilės įgyvendinimas
Prioritetinė eilė gali būti įgyvendinta naudojant masyvą, susietą sąrašą, kaupo duomenų struktūrą arba dvejetainį paieškos medį. Tarp šių duomenų struktūrų krūvos duomenų struktūra leidžia efektyviai įgyvendinti prioritetines eiles.
Taigi, naudosime kaupo duomenų struktūrą, kad įgyvendintume šios pamokos prioritetinę eilę. Didžiausias kaupas yra šiose operacijose. Jei norite sužinoti daugiau apie tai, apsilankykite „max-heap“ ir „mean-heap“.
Toliau pateikiama skirtingų prioritetinės eilės įgyvendinimų lyginamoji analizė.
| Operacijos | žvilgtelėti | Įdėti | Ištrinti |
|---|---|---|---|
| Susietas sąrašas | O(1) | O(n) | O(1) |
| Dvejetainis kaupas | O(1) | O(log n) | O(log n) |
| Dvejetainis paieškos medis | O(1) | O(log n) | O(log n) |
Prioritetinės eilės operacijos
Pagrindinės prioritetinės eilės operacijos yra elementų įterpimas, pašalinimas ir žiūrėjimas.
Prieš pradėdami nagrinėti prioritetinę eilę, ieškokite informacijos apie kaupo duomenų struktūrą, kad geriau suprastumėte dvejetainį kaupą, nes jis naudojamas šiame straipsnyje išdėstytai prioritetinei eilei įgyvendinti.
1. Elemento įterpimas į prioritetinę eilę
Elementas įterpiamas į prioritetinę eilę („max-heap“) atliekant šiuos veiksmus.
- Įterpkite naują elementą medžio gale.
Eilės pabaigoje įterpkite elementą - Sukaupk medį.
Perkelkite įterpę
Elemento įterpimo į prioritetinę eilę algoritmas (maks. Krūva)
Jei nėra mazgo, sukurkite naująNode. dar (mazgas jau yra) įterpkite newNode į pabaigą (paskutinis mazgas iš kairės į dešinę.) sukaupkite masyvą
Min Heap atveju minėtas algoritmas yra modifikuotas taip, kad parentNodevisada būtų mažesnis nei newNode.
2. Elemento ištrynimas iš prioritetinės eilės
Elementas iš prioritetinės eilės („max-heap“) ištrinamas taip:
- Pasirinkite elementą, kurį norite ištrinti.
Pasirinkite elementą, kurį norite ištrinti - Pakeiskite jį su paskutiniu elementu.
Pakeiskite su paskutiniu lapo mazgo elementu - Pašalinkite paskutinį elementą.
Nuimkite paskutinį elemento lapą - Sukaupk medį.
Sumažinkite prioritetinę eilę
Elemento pašalinimo iš prioritetinės eilės algoritmas (maks. Krūva)
Jei „nodeToBeDeleted“ yra „leafNode“, pašalinkite mazgą Else swap
Min Heap atveju minėtas algoritmas yra modifikuotas taip, kad abu childNodesbūtų mažesni nei currentNode.
3. Žiūrėjimas iš prioritetinės eilės (rasti maks. / Min.)
„Peek“ operacija grąžina maksimalų elementą iš „Max Heap“ arba minimalų elementą iš „Min Heap“, neištrindama mazgo.
Tiek Maxui, tiek Minui Heapui
grąžinti rootNode
4. „Extract-Max / Min“ iš prioritetinės eilės
„Extract-Max“ grąžina mazgą su maksimalia verte, pašalinus jį iš „Max Heap“, o „Extract-Min“ grąžina mazgą su minimalia verte, pašalinus jį iš „Min Heap“.
Prioritetinės eilės diegimas Python, Java, C ir 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); )
Prioritetinės eilės programos
Kai kurios prioritetinės eilės programos yra:
- Dijkstros algoritmas
- kamino įgyvendinimui
- apkrovos balansavimui ir pertraukimo valdymui operacinėje sistemoje
- duomenų suglaudinimui Huffmano kodu
