Σε αυτό το σεμινάριο, θα μάθετε πώς λειτουργεί ο αλγόριθμος σωρού σωρού. Επίσης, θα βρείτε λειτουργικά παραδείγματα σωρού σε C, C ++, Java και Python.
Το Heap Sort είναι ένας δημοφιλής και αποτελεσματικός αλγόριθμος ταξινόμησης στον προγραμματισμό υπολογιστών. Η εκμάθηση του τρόπου σύνταξης του αλγόριθμου ταξινόμησης σωρού απαιτεί γνώση δύο τύπων δομών δεδομένων - συστοιχιών και δέντρων.
Το αρχικό σύνολο αριθμών που θέλουμε να ταξινομήσουμε αποθηκεύεται σε έναν πίνακα π.χ. (10, 3, 76, 34, 23, 32)και μετά την ταξινόμηση, λαμβάνουμε έναν ταξινομημένο πίνακα(3,10,23,32,34,76)
Η ταξινόμηση σωρού λειτουργεί οπτικοποιώντας τα στοιχεία του πίνακα ως ένα ειδικό είδος πλήρους δυαδικού δέντρου που ονομάζεται σωρός.
Ως προϋπόθεση, πρέπει να γνωρίζετε για μια πλήρη δυαδική δομή δεδομένων και σωρού δεδομένων.
Σχέση μεταξύ Array Indexes και Tree Elements
Ένα πλήρες δυαδικό δέντρο έχει μια ενδιαφέρουσα ιδιότητα που μπορούμε να χρησιμοποιήσουμε για να βρούμε τα παιδιά και τους γονείς οποιουδήποτε κόμβου.
Εάν το ευρετήριο οποιουδήποτε στοιχείου στον πίνακα είναι i, το στοιχείο στο ευρετήριο 2i+1θα γίνει το αριστερό θυγατρικό και το στοιχείο στο 2i+2ευρετήριο θα γίνει το σωστό παιδί. Επίσης, ο γονέας οποιουδήποτε στοιχείου στο ευρετήριο i δίνεται από το κάτω όριο του (i-1)/2.
Σχέση μεταξύ δεικτών πίνακα και σωρού
Ας το δοκιμάσουμε,
Αριστερό παιδί 1 (ευρετήριο 0) = στοιχείο σε (2 * 0 + 1) ευρετήριο = στοιχείο σε 1 ευρετήριο = 12 Δεξιό παιδί 1 = στοιχείο σε (2 * 0 + 2) ευρετήριο = στοιχείο σε 2 ευρετήριο = 9 Ομοίως, Αριστερό παιδί 12 (δείκτης 1) = στοιχείο σε (2 * 1 + 1) δείκτης = στοιχείο σε 3 δείκτη = 5 Δεξί παιδί 12 = στοιχείο σε (2 * 1 + 2) δείκτης = στοιχείο σε 4 δείκτη = 6
Ας επιβεβαιώσουμε επίσης ότι ισχύουν οι κανόνες για την εύρεση γονέα οποιουδήποτε κόμβου
Γονέας 9 (θέση 2) = (2-1) / 2 = ½ = 0,5 ~ 0 δείκτης = 1 Γονέας 12 (θέση 1) = (1-1) / 2 = 0 δείκτης = 1
Η κατανόηση αυτής της χαρτογράφησης ευρετηρίων συστοιχιών σε θέσεις δέντρου είναι ζωτικής σημασίας για την κατανόηση του τρόπου λειτουργίας της δομής δεδομένων σωρού και του τρόπου με τον οποίο χρησιμοποιείται για την εφαρμογή ταξινόμησης σωρού.
Τι είναι η δομή δεδομένων σωρού;
Το Heap είναι μια ειδική δομή δεδομένων που βασίζεται σε δέντρο. Ένα δυαδικό δέντρο λέγεται ότι ακολουθεί μια δομή δεδομένων σωρού εάν
- είναι ένα πλήρες δυαδικό δέντρο
- Όλοι οι κόμβοι στο δέντρο ακολουθούν την ιδιότητα ότι είναι μεγαλύτεροι από τα παιδιά τους, δηλαδή το μεγαλύτερο στοιχείο είναι στη ρίζα και τα παιδιά του και μικρότερα από τη ρίζα και ούτω καθεξής. Ένας τέτοιος σωρός ονομάζεται μέγιστος σωρός. Αν αντίθετα, όλοι οι κόμβοι είναι μικρότεροι από τα παιδιά τους, ονομάζεται min-heap
Το ακόλουθο παράδειγμα διάγραμμα δείχνει Max-Heap και Min-Heap.
Max Heap και Min Heap
Για να μάθετε περισσότερα σχετικά με αυτό, επισκεφθείτε τη Δομή δεδομένων σωρού.
Πώς να «συσσωρεύσει» ένα δέντρο
Ξεκινώντας από ένα πλήρες δυαδικό δέντρο, μπορούμε να το τροποποιήσουμε ώστε να γίνει Max-Heap εκτελώντας μια συνάρτηση που ονομάζεται heapify σε όλα τα στοιχεία που δεν είναι φύλλα του σωρού.
Δεδομένου ότι το heapify χρησιμοποιεί αναδρομή, μπορεί να είναι δύσκολο να κατανοηθεί. Ας σκεφτούμε λοιπόν πρώτα πώς θα συσσωρεύσετε ένα δέντρο με τρία μόνο στοιχεία.
heapify(array) Root = array(0) Largest = largest( array(0) , array (2*0 + 1). array(2*0+2)) if(Root != Largest) Swap(Root, Largest) 
Βασικές θήκες βάσης
Το παραπάνω παράδειγμα δείχνει δύο σενάρια - ένα στο οποίο η ρίζα είναι το μεγαλύτερο στοιχείο και δεν χρειάζεται να κάνουμε τίποτα. Και ένα άλλο στο οποίο η ρίζα είχε ένα μεγαλύτερο στοιχείο ως παιδί και έπρεπε να ανταλλάξουμε για να διατηρήσουμε την ιδιότητα max-heap
Εάν έχετε δουλέψει με αναδρομικούς αλγόριθμους στο παρελθόν, πιθανότατα έχετε προσδιορίσει ότι πρέπει να είναι η βασική περίπτωση.
Τώρα ας σκεφτούμε ένα άλλο σενάριο στο οποίο υπάρχουν περισσότερα από ένα επίπεδα.
Πώς να συσσωρεύσετε το ριζικό στοιχείο όταν τα δευτερεύοντα δέντρα του είναι ήδη μεγίστοι σωροί
Το κορυφαίο στοιχείο δεν είναι ένα μέγιστο σωρό, αλλά όλα τα δευτερεύοντα δέντρα είναι μεγίστοι σωροί.
Για να διατηρήσουμε την ιδιότητα max-heap για ολόκληρο το δέντρο, θα πρέπει να συνεχίσουμε να πιέζουμε 2 προς τα κάτω μέχρι να φτάσει στη σωστή θέση του.
Πώς να συσσωρεύσετε το ριζικό στοιχείο όταν τα δευτερεύοντα δέντρα του είναι μεγίστοι
Έτσι, για να διατηρήσουμε την ιδιότητα max-heap σε ένα δέντρο όπου και τα δύο υπο-δέντρα είναι max-heaps, πρέπει να τρέξουμε επανειλημμένα το heapify στο ριζικό στοιχείο μέχρι να είναι μεγαλύτερο από τα παιδιά του ή να γίνει ένας κόμβος φύλλων.
Μπορούμε να συνδυάσουμε και τις δύο αυτές συνθήκες σε μια συνάρτηση heapify ως
void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) )
Αυτή η λειτουργία λειτουργεί τόσο για τη βασική θήκη όσο και για ένα δέντρο οποιουδήποτε μεγέθους. Μπορούμε λοιπόν να μετακινήσουμε το ριζικό στοιχείο στη σωστή θέση για να διατηρήσουμε την κατάσταση μέγιστου σωρού για οποιοδήποτε μέγεθος δέντρου, αρκεί τα υποδέντρα να είναι μεγάλα σωρά.
Δημιουργήστε μέγιστο σωρό
Για να δημιουργήσουμε ένα μέγιστο σωρό από οποιοδήποτε δέντρο, μπορούμε έτσι να αρχίσουμε να αυξάνουμε κάθε δευτερεύον δέντρο από κάτω προς τα πάνω και να καταλήγουμε με ένα μέγιστο σωρό αφού εφαρμοστεί η συνάρτηση σε όλα τα στοιχεία, συμπεριλαμβανομένου του ριζικού στοιχείου.
Στην περίπτωση ενός πλήρους δέντρου, ο πρώτος δείκτης ενός κόμβου χωρίς φύλλα δίνεται από n/2 - 1. Όλοι οι άλλοι κόμβοι μετά από αυτό είναι κόμβοι φύλλων και επομένως δεν χρειάζεται να συσσωρευτούν.
Έτσι, μπορούμε να χτίσουμε έναν μέγιστο σωρό ως
// Build heap (rearrange array) for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); 
Δημιουργία πίνακα και υπολογισμός i 
Βήματα για τη δημιουργία μέγιστου σωρού για ταξινόμηση σωρού 
Βήματα για τη δημιουργία μέγιστου σωρού για ταξινόμηση σωρού 
Βήματα για τη δημιουργία μέγιστου σωρού για ταξινόμηση σωρού
Όπως φαίνεται στο παραπάνω διάγραμμα, ξεκινάμε συσσωρεύοντας τα χαμηλότερα μικρότερα δέντρα και σταδιακά ανεβαίνουμε μέχρι να φτάσουμε στο ριζικό στοιχείο.
Εάν έχετε καταλάβει τα πάντα μέχρι εδώ, συγχαρητήρια, είστε στο δρόμο για να αποκτήσετε το είδος του Heap.
Πώς λειτουργεί το Heap Sort;
- Εφόσον το δέντρο ικανοποιεί την ιδιότητα Max-Heap, τότε το μεγαλύτερο αντικείμενο αποθηκεύεται στον ριζικό κόμβο.
- Ανταλλαγή: Αφαιρέστε το ριζικό στοιχείο και τοποθετήστε το στο τέλος της συστοιχίας (θέση n) Τοποθετήστε το τελευταίο στοιχείο του δέντρου (σωρός) στην κενή θέση.
- Αφαίρεση: Μειώστε το μέγεθος του σωρού κατά 1.
- Heapify: Heapify το ριζικό στοιχείο ξανά, έτσι ώστε να έχουμε το υψηλότερο στοιχείο στο root.
- Η διαδικασία επαναλαμβάνεται έως ότου ταξινομηθούν όλα τα στοιχεία της λίστας.
Ανταλλάξτε, αφαιρέστε και Heapify
Ο παρακάτω κώδικας δείχνει τη λειτουργία.
// Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); )
Παραδείγματα Python, Java και C / C ++
Python Java C C ++ # Heap Sort in python def heapify(arr, n, i): # Find largest among root and children 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 # If root is not largest, swap with largest and continue heapifying if largest != i: arr(i), arr(largest) = arr(largest), arr(i) heapify(arr, n, largest) def heapSort(arr): n = len(arr) # Build max heap for i in range(n//2, -1, -1): heapify(arr, n, i) for i in range(n-1, 0, -1): # Swap arr(i), arr(0) = arr(0), arr(i) # Heapify root element heapify(arr, i, 0) arr = (1, 12, 9, 5, 6, 10) heapSort(arr) n = len(arr) print("Sorted array is") for i in range(n): print("%d " % arr(i), end='')
// Heap Sort in Java public class HeapSort ( public void sort(int arr()) ( int n = arr.length; // Build max heap for (int i = n / 2 - 1; i>= 0; i--) ( heapify(arr, n, i); ) // Heap sort for (int i = n - 1; i>= 0; i--) ( int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // Heapify root element heapify(arr, i, 0); ) ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l arr(largest)) largest = l; if (r arr(largest)) largest = r; // Swap and continue heapifying if root is not largest if (largest != i) ( int swap = arr(i); arr(i) = arr(largest); arr(largest) = swap; heapify(arr, n, largest); ) ) // Function to print an array static void printArray(int arr()) ( int n = arr.length; for (int i = 0; i < n; ++i) System.out.print(arr(i) + " "); System.out.println(); ) // Driver code public static void main(String args()) ( int arr() = ( 1, 12, 9, 5, 6, 10 ); HeapSort hs = new HeapSort(); hs.sort(arr); System.out.println("Sorted array is"); printArray(arr); ) )
// Heap Sort in C #include // Function to swap the the position of two elements void swap(int *a, int *b) ( int temp = *a; *a = *b; *b = temp; ) void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(&arr(i), &arr(largest)); heapify(arr, n, largest); ) ) // Main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(&arr(0), &arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) printf("%d ", arr(i)); printf(""); ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); printf("Sorted array is "); printArray(arr, n); )
// Heap Sort in C++ #include using namespace std; void heapify(int arr(), int n, int i) ( // Find largest among root, left child and right child int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left arr(largest)) largest = left; if (right arr(largest)) largest = right; // Swap and continue heapifying if root is not largest if (largest != i) ( swap(arr(i), arr(largest)); heapify(arr, n, largest); ) ) // main function to do heap sort void heapSort(int arr(), int n) ( // Build max heap for (int i = n / 2 - 1; i>= 0; i--) heapify(arr, n, i); // Heap sort for (int i = n - 1; i>= 0; i--) ( swap(arr(0), arr(i)); // Heapify root element to get highest element at root again heapify(arr, i, 0); ) ) // Print an array void printArray(int arr(), int n) ( for (int i = 0; i < n; ++i) cout << arr(i) << " "; cout << ""; ) // Driver code int main() ( int arr() = (1, 12, 9, 5, 6, 10); int n = sizeof(arr) / sizeof(arr(0)); heapSort(arr, n); cout << "Sorted array is "; printArray(arr, n); )
Πολυπλοκότητα ταξινόμησης σωρού
Το Heap Sort έχει O(nlog n)χρονικές περιπλοκές για όλες τις περιπτώσεις (καλύτερη περίπτωση, μέση περίπτωση και χειρότερη περίπτωση).
Ας καταλάβουμε τον λόγο. Το ύψος ενός πλήρους δυαδικού δέντρου που περιέχει n στοιχεία είναιlog n
As we have seen earlier, to fully heapify an element whose subtrees are already max-heaps, we need to keep comparing the element with its left and right children and pushing it downwards until it reaches a point where both its children are smaller than it.
In the worst case scenario, we will need to move an element from the root to the leaf node making a multiple of log(n) comparisons and swaps.
During the build_max_heap stage, we do that for n/2 elements so the worst case complexity of the build_heap step is n/2*log n ~ nlog n.
During the sorting step, we exchange the root element with the last element and heapify the root element. For each element, this again takes log n worst time because we might have to bring the element all the way from the root to the leaf. Since we repeat this n times, the heap_sort step is also nlog n.
Also since the build_max_heap and heap_sort steps are executed one after another, the algorithmic complexity is not multiplied and it remains in the order of nlog n.
Also it performs sorting in O(1) space complexity. Compared with Quick Sort, it has a better worst case ( O(nlog n) ). Quick Sort has complexity O(n^2) for worst case. But in other cases, Quick Sort is fast. Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.
Heap Sort Applications
Systems concerned with security and embedded systems such as Linux Kernel use Heap Sort because of the O(n log n) upper bound on Heapsort's running time and constant O(1) upper bound on its auxiliary storage.
Παρόλο που το Heap Sort έχει O(n log n)χρονική πολυπλοκότητα ακόμη και στη χειρότερη περίπτωση, δεν έχει περισσότερες εφαρμογές (σε σύγκριση με άλλους αλγόριθμους ταξινόμησης όπως Quick Sort, Merge Sort). Ωστόσο, η υποκείμενη δομή δεδομένων του, σωρός, μπορεί να χρησιμοποιηθεί αποτελεσματικά εάν θέλουμε να εξαγάγουμε το μικρότερο (ή μεγαλύτερο) από τη λίστα στοιχείων χωρίς το γενικό κόστος να διατηρούνται τα υπόλοιπα στοιχεία σε ταξινομημένη σειρά. Για παράδειγμα ουρές προτεραιότητας.
