heap sort c with examples
Μια εισαγωγή στο σωρό ταξινόμηση με παραδείγματα.
Το Heapsort είναι μια από τις πιο αποτελεσματικές τεχνικές διαλογής. Αυτή η τεχνική δημιουργεί έναν σωρό από τον δεδομένο μη ταξινομημένο πίνακα και στη συνέχεια χρησιμοποιεί τον σωρό ξανά για να ταξινομήσει τον πίνακα.
Το Heapsort είναι μια τεχνική ταξινόμησης που βασίζεται στη σύγκριση και χρησιμοποιεί δυαδικό σωρό.
=> Διαβάστε το The Easy C ++ Training Series.
πώς να ξεκινήσετε την καριέρα σας στις δοκιμές λογισμικού
Τι θα μάθετε:
- Τι είναι ένας δυαδικός σωρός;
- Γενικός αλγόριθμος
- Απεικόνιση
- Παράδειγμα C ++
- Παράδειγμα Java
- συμπέρασμα
- Συνιστώμενη ανάγνωση
Τι είναι ένας δυαδικός σωρός;
Ένας δυαδικός σωρός αντιπροσωπεύεται χρησιμοποιώντας ένα πλήρες δυαδικό δέντρο. Ένα πλήρες δυαδικό δέντρο είναι ένα δυαδικό δέντρο στο οποίο όλοι οι κόμβοι σε κάθε επίπεδο είναι γεμάτοι εντελώς εκτός από τους κόμβους φύλλων και οι κόμβοι είναι όσο αριστερά.
Ένας δυαδικός σωρός ή απλά ένας σωρός είναι ένα πλήρες δυαδικό δέντρο όπου τα στοιχεία ή οι κόμβοι αποθηκεύονται με τέτοιο τρόπο ώστε ο ριζικός κόμβος να είναι μεγαλύτερος από τους δύο θυγατρικούς κόμβους του. Αυτό ονομάζεται επίσης μέγιστος σωρός.
Τα στοιχεία του δυαδικού σωρού μπορούν επίσης να αποθηκευτούν ως min-heap όπου ο ριζικός κόμβος είναι μικρότερος από τους δύο θυγατρικούς κόμβους του. Μπορούμε να αντιπροσωπεύσουμε έναν σωρό ως δυαδικό δέντρο ή πίνακα.
Ενώ αναπαριστά έναν σωρό ως πίνακα, υποθέτοντας ότι ο δείκτης ξεκινά από το 0, το ριζικό στοιχείο αποθηκεύεται στο 0. Γενικά, εάν ένας γονικός κόμβος βρίσκεται στη θέση Ι, τότε ο αριστερός θυγατρικός κόμβος βρίσκεται στη θέση (2 * I + 1) και ο σωστός κόμβος βρίσκεται στο (2 * I +2).
Γενικός αλγόριθμος
Παρακάτω δίνεται ο γενικός αλγόριθμος για τεχνική ταξινόμησης σωρού.
- Δημιουργήστε έναν μέγιστο σωρό από τα δεδομένα δεδομένα έτσι ώστε η ρίζα να είναι το υψηλότερο στοιχείο του σωρού.
- Αφαιρέστε τη ρίζα, δηλαδή το υψηλότερο στοιχείο από το σωρό και αντικαταστήστε ή αντικαταστήστε το με το τελευταίο στοιχείο του σωρού.
- Στη συνέχεια, προσαρμόστε το μέγιστο σωρό, έτσι ώστε να μην παραβιάσετε τις ιδιότητες μέγιστου σωρού (heapify).
- Το παραπάνω βήμα μειώνει το μέγεθος του σωρού κατά 1.
- Επαναλάβετε τα παραπάνω τρία βήματα έως ότου το μέγεθος του σωρού μειωθεί σε 1.
Όπως φαίνεται στον γενικό αλγόριθμο για να ταξινομήσετε το δεδομένο σύνολο δεδομένων σε αυξανόμενη σειρά, καταρτίζουμε πρώτα έναν μέγιστο σωρό για τα δεδομένα δεδομένα.
Ας πάρουμε ένα παράδειγμα για τη δημιουργία ενός μέγιστου σωρού με το ακόλουθο σύνολο δεδομένων.
6, 10, 2, 4, 1
Μπορούμε να κατασκευάσουμε ένα δέντρο για αυτό το σύνολο δεδομένων ως εξής.
Στην παραπάνω αναπαράσταση δέντρου, οι αριθμοί στις αγκύλες αντιπροσωπεύουν τις αντίστοιχες θέσεις στον πίνακα.
Για να δημιουργήσουμε ένα μέγιστο σωρό της παραπάνω αναπαράστασης, πρέπει να πληρούμε την συνθήκη σωρού ότι ο γονικός κόμβος θα πρέπει να είναι μεγαλύτερος από τους θυγατρικούς κόμβους του. Με άλλα λόγια, πρέπει να «heapify» το δέντρο έτσι ώστε να το μετατρέψουμε σε max-heap.
Μετά την επίστρωση του παραπάνω δέντρου, θα λάβουμε το μέγιστο σωρό όπως φαίνεται παρακάτω.
Όπως φαίνεται παραπάνω, έχουμε δημιουργήσει αυτόν τον μέγιστο σωρό από έναν πίνακα.
Στη συνέχεια, παρουσιάζουμε μια απεικόνιση του σωρού. Έχοντας δει την κατασκευή του max-heap, θα παραλείψουμε τα λεπτομερή βήματα για την κατασκευή ενός max-heap και θα δείξουμε άμεσα το μέγιστο σωρό σε κάθε βήμα.
Απεικόνιση
Εξετάστε την ακόλουθη σειρά στοιχείων. Πρέπει να ταξινομήσουμε αυτόν τον πίνακα χρησιμοποιώντας την τεχνική ταξινόμησης σωρού.
Ας κατασκευάσουμε ένα μέγιστο σωρό όπως φαίνεται παρακάτω για την ταξινόμηση του πίνακα.
Μόλις κατασκευαστεί ο σωρός, το αντιπροσωπεύουμε σε μορφή Array όπως φαίνεται παρακάτω.
Τώρα συγκρίνουμε το 1αγκόμβος (root) με τον τελευταίο κόμβο και μετά αντικαταστήστε τους. Έτσι, όπως φαίνεται παραπάνω, ανταλλάξουμε 17 και 3 έτσι ώστε το 17 να βρίσκεται στην τελευταία θέση και το 3 να είναι στην πρώτη θέση.
Τώρα αφαιρούμε τον κόμβο 17 από το σωρό και το βάζουμε στην ταξινομημένη συστοιχία όπως φαίνεται στο σκιασμένο τμήμα παρακάτω.
Τώρα κατασκευάζουμε ξανά έναν σωρό για τα στοιχεία του πίνακα. Αυτή τη φορά το μέγεθος του σωρού μειώνεται κατά 1 καθώς έχουμε διαγράψει ένα στοιχείο (17) από το σωρό.
Ο σωρός των υπόλοιπων στοιχείων φαίνεται παρακάτω.
Στο επόμενο βήμα, θα επαναλάβουμε τα ίδια βήματα.
Συγκρίνουμε και ανταλλάσσουμε το ριζικό στοιχείο και το τελευταίο στοιχείο στο σωρό.
Μετά την ανταλλαγή, διαγράφουμε το στοιχείο 12 από το σωρό και το μετατοπίζουμε στον ταξινομημένο πίνακα.
Για άλλη μια φορά κατασκευάζουμε έναν μέγιστο σωρό για τα υπόλοιπα στοιχεία όπως φαίνεται παρακάτω.
Τώρα αλλάζουμε τη ρίζα και το τελευταίο στοιχείο, δηλαδή 9 και 3. Μετά την ανταλλαγή, το στοιχείο 9 διαγράφεται από το σωρό και τοποθετείται σε μια ταξινομημένη σειρά.
Σε αυτό το σημείο, έχουμε μόνο τρία στοιχεία στο σωρό όπως φαίνεται παρακάτω.
Ανταλλάξαμε 6 και 3 και διαγράψαμε το στοιχείο 6 από το σωρό και το προσθέσαμε στον ταξινομημένο πίνακα.
επιλογή αλγορίθμου ταξινόμησης c ++
Τώρα κατασκευάζουμε έναν σωρό από τα υπόλοιπα στοιχεία και μετά ανταλλάσσουμε και τα δύο.
Μετά την ανταλλαγή 4 και 3, διαγράφουμε το στοιχείο 4 από το σωρό και το προσθέτουμε στον ταξινομημένο πίνακα. Τώρα έχουμε μόνο έναν κόμβο στον σωρό όπως φαίνεται παρακάτω .
Τώρα λοιπόν με έναν μόνο κόμβο που απομένει, τον διαγράφουμε από το σωρό και τον προσθέτουμε στον ταξινομημένο πίνακα.
Έτσι, το παραπάνω που φαίνεται είναι η ταξινομημένη συστοιχία που έχουμε λάβει ως αποτέλεσμα του είδους σωρού.
Στην παραπάνω εικόνα, ταξινομήσαμε τον πίνακα σε αύξουσα σειρά. Εάν πρέπει να ταξινομήσουμε τον πίνακα σε φθίνουσα σειρά, τότε πρέπει να ακολουθήσουμε τα ίδια βήματα αλλά με το ελάχιστο σωρό.
Ο αλγόριθμος Heapsort είναι πανομοιότυπος με το είδος επιλογής στο οποίο επιλέγουμε το μικρότερο στοιχείο και το τοποθετούμε σε ταξινομημένο πίνακα. Ωστόσο, το είδος σωρού είναι ταχύτερο από το είδος επιλογής όσον αφορά την απόδοση. Μπορούμε να το θέσουμε καθώς το heapsort είναι μια βελτιωμένη έκδοση του είδους επιλογής.
Στη συνέχεια, θα εφαρμόσουμε το Heapsort σε γλώσσα C ++ και Java.
Η πιο σημαντική λειτουργία και στις δύο υλοποιήσεις είναι η συνάρτηση 'heapify'. Αυτή η συνάρτηση καλείται από την κύρια ρουτίνα heapsort για να αναδιατάξει το υποδένδρο μόλις διαγραφεί ένας κόμβος ή όταν έχει δημιουργηθεί ο μέγιστος σωρός.
Όταν έχουμε σωρεύσει το δέντρο σωστά, μόνο τότε θα μπορέσουμε να πάρουμε τα σωστά στοιχεία στις σωστές θέσεις τους και έτσι ο πίνακας θα ταξινομηθεί σωστά.
Παράδειγμα C ++
Ακολουθεί ο κωδικός C ++ για εφαρμογή heapsort.
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i Παραγωγή:
ποιο είναι το καλύτερο καθαριστικό υπολογιστή δωρεάν;
Πίνακας εισόδου
4 17 3 12 9 6
Ταξινομημένος πίνακας
3 4 6 9 12 17
Στη συνέχεια, θα εφαρμόσουμε το heapsort στη γλώσσα Java
Παράδειγμα Java
// Java program to implement Heap Sort class HeapSort { public void heap_sort(int arr()) { int n = arr.length; // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end int temp = arr(0); arr(0) = arr(i); arr(i) = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // heapify the sub-tree void heapify(int arr(), int n, int root) { int largest = root; // Initialize largest as root int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { int swap = arr(root); arr(root) = arr(largest); arr(largest) = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } //print array contents - utility function static void displayArray(int arr()) { int n = arr.length; for (int i=0; i Παραγωγή:
Πίνακας εισαγωγής:
4 17 3 12 9 6
Ταξινομημένος πίνακας:
3 4 6 9 12 17
συμπέρασμα
Το Heapsort είναι μια τεχνική ταξινόμησης βασισμένη σε σύγκριση χρησιμοποιώντας δυαδικό σωρό.
Μπορεί να χαρακτηριστεί ως βελτίωση σε σχέση με το είδος επιλογής, καθώς και οι δύο αυτές τεχνικές ταξινόμησης λειτουργούν με παρόμοια λογική εύρεσης του μεγαλύτερου ή του μικρότερου στοιχείου στον πίνακα επανειλημμένα και, στη συνέχεια, τοποθετώντας το στον ταξινομημένο πίνακα.
Η ταξινόμηση σωρού χρησιμοποιεί το μέγιστο σωρό ή το ελάχιστο σωρό για την ταξινόμηση του πίνακα. Το πρώτο βήμα στην ταξινόμηση σωρού είναι να δημιουργήσετε έναν ελάχιστο ή μέγιστο σωρό από τα δεδομένα του πίνακα και στη συνέχεια να διαγράψετε το ριζικό στοιχείο αναδρομικά και να συσσωρεύσετε το σωρό έως ότου υπάρχει μόνο ένας κόμβος στο σωρό.
Το Heapsort είναι ένας αποτελεσματικός αλγόριθμος και αποδίδει ταχύτερα από το είδος επιλογής. Μπορεί να χρησιμοποιηθεί για να ταξινομήσετε έναν σχεδόν ταξινομημένο πίνακα ή να βρείτε k μεγαλύτερα ή μικρότερα στοιχεία στον πίνακα.
Με αυτό, ολοκληρώσαμε το θέμα μας σχετικά με τις τεχνικές ταξινόμησης στο C ++. Από το επόμενο σεμινάριό μας και μετά, θα ξεκινήσουμε με δομές δεδομένων ένα προς ένα.
=> Αναζητήστε ολόκληρη τη σειρά προπόνησης C ++ εδώ.
Συνιστώμενη ανάγνωση
- MongoDB Sort () Μέθοδος με παραδείγματα
- Unix Sort Command με Σύνταξη, Επιλογές και Παραδείγματα
- Συγχώνευση ταξινόμησης σε C ++ με παραδείγματα
- Ταξινόμηση κελύφους σε C ++ με παραδείγματα
- Εισαγωγή Ταξινόμηση σε C ++ με παραδείγματα
- Επιλογή Ταξινόμηση σε C ++ με παραδείγματα
- Ταξινόμηση Bubble σε C ++ με παραδείγματα
- Γρήγορη ταξινόμηση σε C ++ με παραδείγματα