Σε αυτό το σεμινάριο, θα μάθετε τι είναι η ουρά προτεραιότητας. Επίσης, θα μάθετε για τις υλοποιήσεις του σε Python, Java, C και C ++.
Η ουρά προτεραιότητας είναι ένας ειδικός τύπος ουράς στην οποία κάθε στοιχείο συνδέεται με μια προτεραιότητα και προβάλλεται σύμφωνα με την προτεραιότητά του. Εάν εμφανιστούν στοιχεία με την ίδια προτεραιότητα, προβάλλονται σύμφωνα με τη σειρά τους στην ουρά.
Γενικά, η τιμή του ίδιου του στοιχείου θεωρείται για την εκχώρηση της προτεραιότητας.
Για παράδειγμα, το στοιχείο με την υψηλότερη τιμή θεωρείται ως το στοιχείο υψηλότερης προτεραιότητας. Ωστόσο, σε άλλες περιπτώσεις, μπορούμε να υποθέσουμε το στοιχείο με τη χαμηλότερη τιμή ως στοιχείο υψηλότερης προτεραιότητας. Σε άλλες περιπτώσεις, μπορούμε να θέσουμε προτεραιότητες σύμφωνα με τις ανάγκες μας.
Κατάργηση στοιχείου υψηλότερης προτεραιότητας
Διαφορά μεταξύ ουράς προτεραιότητας και κανονικής ουράς
Σε μια ουρά, εφαρμόζεται ο κανόνας first-in-first-out ενώ, σε μια ουρά προτεραιότητας, οι τιμές καταργούνται βάσει προτεραιότητας . Το στοιχείο με την υψηλότερη προτεραιότητα καταργείται πρώτα.
Εφαρμογή ουράς προτεραιότητας
Η ουρά προτεραιότητας μπορεί να εφαρμοστεί χρησιμοποιώντας έναν πίνακα, μια συνδεδεμένη λίστα, μια δομή δεδομένων σωρού ή ένα δυαδικό δέντρο αναζήτησης. Μεταξύ αυτών των δομών δεδομένων, η δομή δεδομένων σωρού παρέχει μια αποτελεσματική εφαρμογή των ουρών προτεραιότητας.
Ως εκ τούτου, θα χρησιμοποιήσουμε τη δομή δεδομένων σωρού για να εφαρμόσουμε την ουρά προτεραιότητας σε αυτό το σεμινάριο. Ένα μέγιστο σωρό είναι υλοποίηση στις ακόλουθες λειτουργίες. Αν θέλετε να μάθετε περισσότερα σχετικά με αυτό, επισκεφτείτε το max-heap και το mean-heap.
Παρακάτω δίνεται μια συγκριτική ανάλυση διαφορετικών εφαρμογών της ουράς προτεραιότητας.
| Λειτουργίες | κρυφοκοίταγμα | εισάγετε | διαγράφω |
|---|---|---|---|
| Συνδεδεμένη λίστα | O(1) | O(n) | O(1) |
| Δυαδικός σωρός | O(1) | O(log n) | O(log n) |
| Δυαδικό δέντρο αναζήτησης | O(1) | O(log n) | O(log n) |
Λειτουργίες ουράς προτεραιότητας
Οι βασικές λειτουργίες μιας ουράς προτεραιότητας είναι η εισαγωγή, η αφαίρεση και η παρακολούθηση στοιχείων.
Πριν μελετήσετε την ουρά προτεραιότητας, ανατρέξτε στη δομή δεδομένων σωρού για καλύτερη κατανόηση του δυαδικού σωρού καθώς χρησιμοποιείται για την εφαρμογή της ουράς προτεραιότητας σε αυτό το άρθρο.
1. Εισαγωγή στοιχείου στην ουρά προτεραιότητας
Η εισαγωγή ενός στοιχείου σε μια ουρά προτεραιότητας (max-heap) γίνεται με τα ακόλουθα βήματα.
- Εισαγάγετε το νέο στοιχείο στο τέλος του δέντρου.
Εισαγάγετε ένα στοιχείο στο τέλος της ουράς - Σώστε το δέντρο.
Σκουπίστε μετά την εισαγωγή
Αλγόριθμος για εισαγωγή στοιχείου στην ουρά προτεραιότητας (max-heap)
Εάν δεν υπάρχει κόμβος, δημιουργήστε έναν νέο κόμβο. αλλιώς (υπάρχει ήδη ένας κόμβος) εισάγετε τον νέο κόμβο στο τέλος (τελευταίος κόμβος από αριστερά προς τα δεξιά.)
Για το Min Heap, ο παραπάνω αλγόριθμος τροποποιείται έτσι ώστε να parentNodeείναι πάντα μικρότερος από newNode.
2. Διαγραφή στοιχείου από την ουρά προτεραιότητας
Η διαγραφή ενός στοιχείου από μια ουρά προτεραιότητας (max-heap) γίνεται ως εξής:
- Επιλέξτε το στοιχείο που θα διαγραφεί.
Επιλέξτε το στοιχείο που θα διαγραφεί - Ανταλλάξτε το με το τελευταίο στοιχείο.
Ανταλλαγή με το τελευταίο στοιχείο κόμβου φύλλων - Αφαιρέστε το τελευταίο στοιχείο.
Αφαιρέστε το τελευταίο φύλλο στοιχείου - Σώστε το δέντρο.
Απλοποιήστε την ουρά προτεραιότητας
Αλγόριθμος για διαγραφή ενός στοιχείου στην ουρά προτεραιότητας (max-heap)
Εάν το nodeToBeDeleted είναι το φύλλοNode αφαιρέστε τον κόμβο Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
Για το Min Heap, ο παραπάνω αλγόριθμος τροποποιείται έτσι ώστε και οι δύο να childNodesείναι μικρότεροι από currentNode.
3. Αναζητώντας από την ουρά προτεραιότητας (Εύρεση μέγ. / Λεπτό)
Η λειτουργία Peek επιστρέφει το μέγιστο στοιχείο από το Max Heap ή το ελάχιστο στοιχείο από το Min Heap χωρίς να διαγραφεί ο κόμβος.
Και για το Max heap και το Min Heap
επιστροφή rootNode
4. Εξαγωγή-Max / Min από την ουρά προτεραιότητας
Το Extract-Max επιστρέφει τον κόμβο με τη μέγιστη τιμή μετά την αφαίρεσή του από ένα Max Heap ενώ το Extract-Min επιστρέφει τον κόμβο με την ελάχιστη τιμή μετά την αφαίρεσή του από το Min Heap.
Εφαρμογές ουράς προτεραιότητας σε Python, Java, C και 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); )
Εφαρμογές ουράς προτεραιότητας
Μερικές από τις εφαρμογές μιας ουράς προτεραιότητας είναι:
- Ο αλγόριθμος της Dijkstra
- για εφαρμογή στοίβας
- για εξισορρόπηση φορτίου και διακοπή χειρισμού σε λειτουργικό σύστημα
- για συμπίεση δεδομένων σε κώδικα Huffman
