Selles õpetuses saate teada, mis on prioriteetne järjekord. Samuti saate teada selle rakendustest Pythonis, Java-s, C-s ja C ++.
Prioriteedijärjekord on eritüüpi järjekord, milles iga element on seotud prioriteediga ja teenindatakse vastavalt selle prioriteedile. Kui esinevad sama prioriteediga elemendid, serveeritakse neid vastavalt järjekorrale järjekorras.
Üldiselt võetakse prioriteedi määramisel arvesse elemendi enda väärtust.
Näiteks peetakse kõrgeima prioriteediga elemendiks kõrgeima väärtusega elementi. Kuid muudel juhtudel võime kõrgeima prioriteediga elemendiks võtta madalaima väärtusega elemendi. Muudel juhtudel saame prioriteedid seada vastavalt oma vajadustele.
Kõrgeima prioriteediga elemendi eemaldamine
Prioriteetse ja normaalse järjekorra erinevus
Järjekorras rakendatakse reegel "esimene sisse-esimesena" , prioriteetses järjekorras eemaldatakse väärtused prioriteedi alusel . Kõigepealt eemaldatakse kõrgeima prioriteediga element.
Prioriteedijärjekorra rakendamine
Prioriteetset järjekorda saab rakendada massiivi, lingitud loendi, kuhja andmestruktuuri või binaarse otsingupuu abil. Nende andmestruktuuride hulgast saab kuhjaga andmestruktuuri prioriteetsete järjekordade tõhusaks rakendamiseks.
Seega kasutame selles õpetuses prioriteetse järjekorra rakendamiseks kuhja andmestruktuuri. Maksimaalne hunnik on tööriist järgmistes toimingutes. Kui soovite selle kohta lisateavet, külastage palun max-heap ja mean-heap.
Allpool on toodud prioriteetse järjekorra erinevate rakenduste võrdlev analüüs.
| Operatsioonid | piiluma | sisestada | kustuta |
|---|---|---|---|
| Lingitud loend | O(1) | O(n) | O(1) |
| Binaarne hunnik | O(1) | O(log n) | O(log n) |
| Binaarotsingupuu | O(1) | O(log n) | O(log n) |
Prioriteedijärjekorra toimingud
Prioriteedijärjekorra põhitoimingud on elementide sisestamine, eemaldamine ja piilumine.
Enne prioriteedijärjekorra uurimist vaadake binaarhunniku paremaks mõistmiseks kuhja andmestruktuuri, kuna seda kasutatakse selles artiklis prioriteetsuse järjekorra rakendamiseks.
1. Lisage element prioriteedijärjekorda
Elemendi sisestamine prioriteetsesse järjekorda (max-heap) toimub järgmiste sammudega.
- Sisestage uus element puu otsa.
Sisestage järjekorra lõppu element - Hange puu.
Heapify pärast sisestamist
Algoritm elemendi lisamiseks prioriteetsesse järjekorda (max-heap)
Kui sõlme pole, looge uusNode. muul viisil (sõlm on juba olemas) sisestage uusNode lõppu (viimane sõlm vasakult paremale.) massiivi kuhjamine
Min Heap'i puhul muudetakse ülaltoodud algoritmi nii, et see parentNodeoleks alati väiksem kui newNode.
2. Elemendi kustutamine prioriteetsest järjekorrast
Element kustutatakse prioriteetsest järjekorrast (max-heap) järgmiselt:
- Valige kustutatav element.
Valige kustutatav element - Vahetage see viimase elemendiga.
Vahetage viimase lehesõlme elemendiga - Eemaldage viimane element.
Eemaldage viimane elemendi leht - Hange puu.
Hange prioriteetset järjekorda
Algoritm elemendi kustutamiseks prioriteedijärjekorras (max-heap)
Kui nodeToBeDeleted on leafNode, eemaldage sõlm NodeToBeDeleted koos lastLeafNode eemalda
Min Heap'i puhul muudetakse ülaltoodud algoritmi nii, et mõlemad childNodesoleksid väiksemad kui currentNode.
3. Prioriteedijärjekorrast piilumine (Leia max / min)
Peek-operatsioon tagastab maksimaalse elemendi maksimaalsest hunnikust või minimaalse elemendi mineraalsest hulgast sõlme kustutamata.
Nii Max kuhja kui ka Min Heap jaoks
tagastage rootNode
4. Extract-Max / Min prioriteedijärjekorrast
Extract-Max tagastab maksimaalse väärtusega sõlme pärast selle eemaldamist Max Heap'ist, samas kui Extract-Min tagastab minimaalse väärtusega sõlme pärast Min Heapist eemaldamist.
Prioriteedijärjekorra rakendused Pythonis, Java-s, C-s ja C ++ -s
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); )
Prioriteedijärjekorra rakendused
Mõned prioriteetse järjekorra rakendused on järgmised:
- Dijkstra algoritm
- virna rakendamiseks
- koormuse tasakaalustamiseks ja katkestuste käsitsemiseks opsüsteemis
- andmete tihendamiseks Huffmani koodis
