Αλγόριθμος ταξινόμησης σωρών (με κωδικό μέσα Python και C++)

Τι είναι ο αλγόριθμος ταξινόμησης σωρών;

Το Heap Sort είναι ένας από τους δημοφιλείς και ταχύτερους αλγόριθμους ταξινόμησης. Είναι χτισμένο πάνω στην πλήρη δομή δεδομένων δυαδικού δέντρου. Θα αναζητήσουμε το μέγιστο στοιχείο και θα το βάλουμε στην κορυφή για το μέγιστο σωρό. Θα το βάλουμε στον γονικό κόμβο του δυαδικού δέντρου.

Ας πούμε ότι δίνεται ένας πίνακας, δεδομένα = [10,5, 7, 9, 4, 11, 45, 17, 60].

Στον πίνακα, αν ο δείκτης i-ο (i=0,1,2,3…) είναι γονικός κόμβος, τότε, (2i+1) και (2i+2) θα είναι το αριστερό και το δεξί τέκνο. Η δημιουργία ενός πλήρους δυαδικού δέντρου με αυτόν τον πίνακα θα μοιάζει με αυτό:

Θα κάνουμε τη διαδικασία heapify από την αρχή μέχρι το τέλος του πίνακα. Αρχικά, αν μετατρέψουμε τον πίνακα σε δέντρο, θα μοιάζει με το παραπάνω. Μπορούμε να δούμε ότι δεν διατηρεί καμία ιδιότητα σωρού (min-heap ή max heap). Θα λάβουμε τον ταξινομημένο πίνακα κάνοντας τη διαδικασία heapify για όλους τους κόμβους.

Εφαρμογή Ταξινόμησης Σωρών

Ακολουθεί κάποια χρήση του αλγόριθμου ταξινόμησης σωρού:

Η κατασκευή «Ουρών προτεραιότητας» χρειάζεται ταξινόμηση σωρών. Επειδή το heapsort διατηρεί το στοιχείο ταξινομημένο μετά από κάθε εισαγωγή.
Η Δομή Δεδομένων Σωρού είναι αποτελεσματική στην εύρεση του k^th μεγαλύτερο στοιχείο σε έναν δεδομένο πίνακα.
Ο πυρήνας Linux χρησιμοποιεί την ταξινόμηση σωρού ως προεπιλογή αλγόριθμος ταξινόμησης καθώς έχει Ο (1) πολυπλοκότητα χώρου.

Δημιουργία Ταξινόμησης Σωρών με Παράδειγμα

Εδώ, θα κατασκευάσουμε έναν μέγιστο σωρό από το ακόλουθο πλήρες δυαδικό δέντρο.

Οι κόμβοι φύλλων είναι 17, 60, 4, 11 και 45. Δεν έχουν θυγατρικούς κόμβους. Γι' αυτό είναι κόμβοι φύλλων. Έτσι, θα ξεκινήσουμε τη μέθοδο heapify από τον γονικό κόμβο τους. Εδώ είναι τα βήματα:

Βήμα 1) Επιλέξτε το αριστερό δευτερεύον δέντρο. Εάν οι θυγατρικοί κόμβοι είναι μεγαλύτεροι, αλλάξτε τον γονικό κόμβο με τον θυγατρικό κόμβο.

Εδώ ο γονικός κόμβος είναι 9. Και οι θυγατρικοί κόμβοι είναι 17 και 60. Καθώς, ο 60 είναι ο μεγαλύτερος, το 60 και το 9 θα εναλλάσσονται για να διατηρηθεί το μέγιστο σωρό.

Βήμα 2) Τώρα, το πιο αριστερό υποδέντρο έχει συσσωρευτεί. Ο επόμενος γονικός κόμβος είναι 7. Αυτός ο γονέας έχει δύο θυγατρικούς κόμβους και ο μεγαλύτερος είναι 45. Άρα, το 45 και το 7 θα εναλλάσσονται.

Βήμα 3) Οι κόμβοι 60 και 4 έχουν τον γονικό κόμβο 5. Καθώς το "5" είναι μικρότερο από τον θυγατρικό κόμβο 60, θα αντικατασταθεί.

Βήμα 4) Τώρα, ο κόμβος 5 έχει τον θυγατρικό κόμβο 17,9. Αυτό δεν είναι διατήρηση της ιδιότητας μέγιστου σωρού. Άρα, το 5 θα αντικατασταθεί με το 17.

Βήμα 5) Ο κόμβος 10 θα αντικατασταθεί με το 60 και μετά θα αντικατασταθεί με το 17. Η διαδικασία θα μοιάζει με την ακόλουθη.

Βήμα 6) Μέχρι το βήμα 5, δημιουργήσαμε το μέγιστο σωρό. Κάθε γονικός κόμβος είναι μεγαλύτερος από τους θυγατρικούς του κόμβους. Ο ριζικός κόμβος έχει τη μέγιστη τιμή (60).

Σημείωση: Για να δημιουργήσουμε τον ταξινομημένο πίνακα, πρέπει να αντικαταστήσουμε τον κόμβο μέγιστης αξίας με τον διάδοχό του.

Αυτή η διαδικασία ονομάζεται "εξαγωγή μέγ". Καθώς το 60 είναι ο μέγιστος κόμβος, θα καθορίσουμε τη θέση του στον 0ο δείκτη και θα δημιουργήσουμε το σωρό χωρίς τον κόμβο 60.

Βήμα 7) Καθώς το 60 αφαιρείται, τότε η επόμενη μέγιστη τιμή είναι 45. Θα κάνουμε ξανά τη διαδικασία «Εξαγωγή μέγιστου» από τον κόμβο 45.

Αυτή τη φορά θα πάρουμε 45 και θα αντικαταστήσουμε τον ριζικό κόμβο με τον διάδοχό του 17.

Πρέπει να εκτελέσουμε "Extract Max” μέχρι να ταξινομηθούν όλα τα στοιχεία.

Αφού κάνουμε αυτά τα βήματα μέχρι να εξαγάγουμε όλες τις μέγιστες τιμές, θα λάβουμε τον παρακάτω πίνακα.

Τι είναι το Binary Heap;

Ένας δυαδικός σωρός είναι ένα είδος ολοκληρωμένου δυαδικό δέντρο δομή δεδομένων. Σε αυτό το είδος δενδρικής δομής, ο γονικός κόμβος είναι είτε μεγαλύτερος είτε μικρότερος από τους θυγατρικούς κόμβους. Εάν ο γονικός κόμβος είναι μικρότερος, τότε ο σωρός ονομάζεται "Min Heap" και εάν ο γονικός κόμβος είναι μεγαλύτερος, ο σωρός ονομάζεται "Max Heap".

Ακολουθούν παραδείγματα ελάχιστου σωρού και μέγιστου σωρού.

Στο παραπάνω σχήμα, αν παρατηρήσετε το "Min Heap", ο γονικός κόμβος είναι πάντα μικρότερος από τους θυγατρικούς του κόμβους. Στην κορυφή του δέντρου, μπορούμε να βρούμε τη μικρότερη τιμή 10.

Ομοίως, για το "Max Heap", ο γονικός κόμβος είναι πάντα μεγαλύτερος από τους θυγατρικούς κόμβους. Το μέγιστο στοιχείο υπάρχει στον κύριο κόμβο για το "Max Heap".

Τι είναι το "Heapify";

Το "Heapify" είναι η αρχή του σωρού που εξασφαλίζει τη θέση του κόμβου. Στο Heapify, ένας μέγιστος σωρός διατηρεί πάντα μια σχέση με τον γονέα και το παιδί, και αυτό σημαίνει ότι ο γονικός κόμβος θα είναι μεγαλύτερος από τους θυγατρικούς κόμβους.

Για παράδειγμα, εάν προστεθεί ένας νέος κόμβος, πρέπει να αναδιαμορφώσουμε το σωρό. Ωστόσο, μπορεί να χρειαστεί να αλλάξουμε ή να αλλάξουμε τους κόμβους ή να αναδιατάξουμε τον πίνακα. Αυτή η διαδικασία αναμόρφωσης ενός σωρού ονομάζεται "heapify".

Ακολουθεί ένα παράδειγμα του πώς λειτουργεί το heapify:

Προσθήκη νέου κόμβου και Heapify — Προσθήκη νέου κόμβου και heapify

Ακολουθούν τα βήματα για το heapify:

Βήμα 1) Προστέθηκε ο κόμβος 65 ως το σωστό παιδί του κόμβου 60.

Βήμα 2) Ελέγξτε εάν ο κόμβος που προστέθηκε πρόσφατα είναι μεγαλύτερος από τον γονικό.

Βήμα 3) Καθώς είναι μεγαλύτερος από τον γονικό κόμβο, ανταλλάξαμε το σωστό παιδί με τον γονέα του.

Πώς να φτιάξετε το Heap

Πριν χτίσουμε το σωρό ή γεμίσουμε ένα δέντρο, πρέπει να ξέρουμε πώς θα το αποθηκεύσουμε. Καθώς ο σωρός είναι ένα πλήρες δυαδικό δέντρο, είναι καλύτερο να χρησιμοποιήσετε ένα παράταξη για να κρατήσει τα δεδομένα του σωρού.

Ας υποθέσουμε ότι ένας πίνακας περιέχει συνολικά n στοιχεία. Εάν ο δείκτης "i" είναι γονικός κόμβος, τότε ο αριστερός κόμβος θα βρίσκεται στο ευρετήριο (2i+1), και ο δεξιός κόμβος θα βρίσκεται στο ευρετήριο (2i+2). Υποθέτουμε ότι ο δείκτης του πίνακα ξεκινά από το 0.

Χρησιμοποιώντας αυτό, ας αποθηκεύσουμε έναν μέγιστο σωρό σε έναν πίνακα σαν τον ακόλουθο:

Αναπαράσταση του Max Heap βάσει πίνακα — Αναπαράσταση του μέγιστου σωρού βάσει πίνακα

Ο αλγόριθμος heapify διατηρεί την ιδιότητα heap. Εάν ο γονέας δεν έχει την ακραία τιμή (μικρότερη ή μεγαλύτερη), θα αντικατασταθεί με τον πιο ακραίο θυγατρικό κόμβο.

Ακολουθούν τα βήματα για τη συσσώρευση ενός μέγιστου σωρού:

Βήμα 1) Ξεκινήστε από τον κόμβο φύλλων.

Βήμα 2) Βρείτε το μέγιστο μεταξύ γονέα και παιδιών.

Βήμα 3) Αλλάξτε τους κόμβους εάν ο θυγατρικός κόμβος έχει μεγαλύτερη τιμή από τον γονέα.

Βήμα 4) Ανεβείτε ένα επίπεδο.

Βήμα 5) Ακολουθήστε τα βήματα 2,3,4 μέχρι να φτάσουμε στο δείκτη 0 ή να ταξινομήσουμε ολόκληρο το δέντρο.

Ακολουθεί ο ψευδοκώδικας για το αναδρομικό σωρό (max heap):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Ψευδοκώδικας για ταξινόμηση σωρών

Ακολουθεί ο ψευδοκώδικας για τον αλγόριθμο ταξινόμησης σωρού:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Παράδειγμα κώδικα ταξινόμησης σωρού στο C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Παραγωγή:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Παράδειγμα κώδικα ταξινόμησης σωρού στο Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Παραγωγή:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Ανάλυση πολυπλοκότητας χρόνου και χώρου του Heap Sort

Υπάρχει πολυπλοκότητα χρόνου και χωρικής πολυπλοκότητας που μπορούμε να αναλύσουμε για την ταξινόμηση σωρού. Για χρονική πολυπλοκότητα έχουμε τις εξής περιπτώσεις:

καλυτερα Case
Μέση περίπτωση
Χειρότερη περίπτωση

Ο σωρός υλοποιείται σε ένα πλήρες δυαδικό δέντρο. Έτσι, στο κάτω επίπεδο του δυαδικού δέντρου, θα υπάρχει ο μέγιστος αριθμός κόμβων. Εάν το κάτω επίπεδο έχει n κόμβους, τότε το παραπάνω επίπεδο θα έχει n/2 κόμβους.

Σε αυτό το παράδειγμα, το Επίπεδο 3 έχει τέσσερα στοιχεία, το επίπεδο 2 έχει δύο στοιχεία και το επίπεδο 1 έχει ένα στοιχείο. Εάν υπάρχει ένας συνολικός αριθμός n στοιχείων, το ύψος ή το συνολικό επίπεδο θα είναι Ιστορικό₂(ν). Έτσι, η εισαγωγή ενός μεμονωμένου στοιχείου θα μπορούσε να απαιτήσει το πολύ Log(n) επαναλήψεις.

Όταν θέλουμε να πάρουμε τη μέγιστη τιμή από το σωρό, παίρνουμε απλώς τον ριζικό κόμβο. Στη συνέχεια, εκτελέστε ξανά το heapify. Κάθε heapify παίρνει Ιστορικό₂(η) χρόνος. Η εξαγωγή του μέγιστου απαιτεί χρόνο O(1).

Καλυτερα Case Time Complexity for Heap Sort Algorithm

Όταν όλα τα στοιχεία είναι ήδη ταξινομημένα στον πίνακα, θα χρειαστεί χρόνος O(n) για τη δημιουργία του σωρού. Διότι εάν η λίστα είναι ταξινομημένη τότε η εισαγωγή ενός στοιχείου θα πάρει τον σταθερό χρόνο που είναι O(1).

Έτσι, θα χρειαστεί χρόνος O(n) για να δημιουργηθεί ένας μέγιστος σωρός ή ένας ελάχιστος σωρός στην καλύτερη περίπτωση.

Μέση πολυπλοκότητα χρόνου υπόθεσης για αλγόριθμο ταξινόμησης σωρού

Η εισαγωγή ενός στοιχείου ή η εξαγωγή ενός μέγιστου κοστίζει χρόνο O(log(n)). Έτσι, η μέση πολυπλοκότητα χρόνου περίπτωσης για τον αλγόριθμο ταξινόμησης σωρού είναι O(n log(n)).

Χειρότερη περίπτωση πολυπλοκότητας χρόνου για αλγόριθμο ταξινόμησης σωρών

Παρόμοια με τη μέση περίπτωση, στο χειρότερο σενάριο, θα μπορούσαμε να εκτελέσουμε heapify n φορές. Κάθε heapify θα κοστίζει O(log(n)) χρόνο. Έτσι, η χειρότερη χρονική πολυπλοκότητα θα είναι O(n log(n)).

Πολυπλοκότητα χώρου για αλγόριθμο ταξινόμησης σωρού

Η ταξινόμηση σωρού είναι ένας επί τόπου σχεδιασμένος αλγόριθμος. Αυτό σημαίνει ότι δεν απαιτείται επιπλέον ή προσωρινή μνήμη για την εκτέλεση της εργασίας. Αν δούμε την υλοποίηση, θα παρατηρήσουμε ότι χρησιμοποιήσαμε το swap () για να πραγματοποιήσουμε την ανταλλαγή των κόμβων. Δεν χρειαζόταν άλλη λίστα ή πίνακας. Άρα, η πολυπλοκότητα του χώρου είναι Ο(1).

Μπορεί να σας αρέσει: