Δομή Δεδομένων Σωρού: Τι είναι το Σωρό;

Τι είναι μια δομή δεδομένων σωρού;

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

Με απλά λόγια, ένα Heap είναι ένα πλήρες δυαδικό δέντρο που ικανοποιεί την ιδιότητα heap: κάθε γονέας διατάσσεται σταθερά έναντι των παιδιών του, γεγονός που το καθιστά ιδανικό για ουρές προτεραιότητας και ταξινόμηση heap.

Γιατί χρειάζεστε τη Δομή Δεδομένων Σωρού;

Ακολουθούν οι κύριοι λόγοι για τη χρήση ενός Heap:

• Η δομή δεδομένων σωρού επιτρέπει τη διαγραφή και την εισαγωγή σε λογαριθμικό χρόνο – O(log₂ν).
• Τα δεδομένα στο δέντρο είναι ταξινομημένα με μια συγκεκριμένη σειρά. Εκτός από την ενημέρωση ή την υποβολή ερωτημάτων για τιμές όπως το μέγιστο ή το ελάχιστο, ο προγραμματιστής μπορεί να βρει σχέσεις μεταξύ του γονέα και του απογόνου.
• Μπορείτε να εφαρμόσετε την έννοια του Μοντέλο αντικειμένου εγγράφου για να σας βοηθήσει να κατανοήσετε οπτικά τη δομή δεδομένων σωρού.
• Οι σωροί υποστηρίζουν αποτελεσματικές λειτουργίες ουράς προτεραιότητας, οι οποίες είναι κρίσιμες για αλγόριθμους γραφημάτων όπως η συντομότερη διαδρομή του Dijkstra και το ελάχιστο δέντρο επέκτασης του Prim.

Τύποι Σωρών

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

• Ουρά προτεραιότητας: Είναι κοιλιακοίtracΔομή δεδομένων t που περιέχει αντικείμενα με προτεραιότητα. Κάθε αντικείμενο ή στοιχείο έχει μια προκαθορισμένη προτεραιότητα. Επομένως, το αντικείμενο ή το στοιχείο στο οποίο έχει εκχωρηθεί η υψηλότερη προτεραιότητα λαμβάνει την υπηρεσία πριν από τα υπόλοιπα.
• Δυαδική σωρό: Οι δυαδικοί σωροί είναι κατάλληλοι για απλές λειτουργίες σωρού, όπως διαγραφές και εισαγωγές. Αποτελούν την προεπιλεγμένη υλοποίηση πίσω από τις περισσότερες τυπικές ουρές προτεραιότητας βιβλιοθηκών.
• Διωνυμικός σωρός: Ένας διωνυμικός σωρός αποτελείται από μια σειρά συλλογών διωνυμικών δέντρων που αποτελούν τον σωρό. Ένα διωνυμικό δέντρο σωρού δεν είναι ένα συνηθισμένο δέντρο, όπως ορίζεται αυστηρά. Ο συνολικός αριθμός στοιχείων σε ένα διωνυμικό δέντρο ισούται πάντα με 2.ⁿ κόμβους.
• Ταξινόμηση σωρού: Σε αντίθεση με τους περισσότερους αλγόριθμους ταξινόμησης, η Ταξινόμηση Σωρού χρησιμοποιεί χώρο O(1) για τη λειτουργία ταξινόμησης. Είναι ένας αλγόριθμος ταξινόμησης που βασίζεται σε συγκρίσεις, όπου η ταξινόμηση πραγματοποιείται σε αύξουσα σειρά, μετατρέποντας πρώτα την είσοδο σε Max-Heap. Μπορείτε να εξετάσετε την Ταξινόμηση Σωρού ως ένα αναβαθμισμένο δυαδικό δέντρο αναζήτησης.

Συνήθως, μια δομή δεδομένων σωρού χρησιμοποιεί δύο στρατηγικές. Για την είσοδο 12 – 8 – 4 – 2 και 1:

• Ελάχιστη σωρό – η ελάχιστη τιμή στην κορυφή
• Max-Heap – η υψηλότερη τιμή στην κορυφή

Ελάχιστη σωρό

Στη δομή Min-Heap, ο κόμβος ρίζας έχει τιμή είτε ίση είτε μικρότερη από τα παιδιά αυτού του κόμβου. Επομένως, η ρίζα ενός Min-Heap κατέχει την ελάχιστη τιμή. Το Min-Heap είναι επίσης ένα πλήρες δυαδικό δέντρο.

Μόλις έχετε ένα Min-Heap σε ένα δέντρο, όλα τα φύλλα είναι βιώσιμα υποψήφια για τη μέγιστη τιμή. Ωστόσο, πρέπει να εξετάσετε κάθε φύλλο για να λάβετε την ακριβή τιμή Max-Heap.

Παράδειγμα Min-Heap

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

Ας υποθέσουμε ότι αποθηκεύετε τα στοιχεία στον πίνακα Array_N[12, 2, 8, 1, 4]. Όπως μπορείτε να δείτε από τον πίνακα, το στοιχείο root παραβιάζει την προτεραιότητα Min-Heap. Για να διατηρήσετε την ιδιότητα Min-Heap, πρέπει να εκτελέσετε τις λειτουργίες min-heapify για να εναλλάξετε τα στοιχεία μέχρι να ικανοποιηθούν οι κανόνες Min-Heap.

Max-Heap

Στη δομή Max-Heap, ο γονικός ή ριζικός κόμβος έχει τιμή ίση ή μεγαλύτερη από τις τιμές των παιδιών του. Αυτός ο κόμβος κατέχει τη μέγιστη τιμή. Είναι ένα πλήρες δυαδικό δέντρο, επομένως μπορείτε να δημιουργήσετε ένα Max-Heap από μια συλλογή τιμών σε χρόνο O(n).

Ακολουθούν μερικές μέθοδοι που χρησιμοποιούνται συνήθως κατά την εφαρμογή ενός Java Μέγιστος-σωρός:

• Προσθήκη (): Τοποθετεί ένα νέο στοιχείο σε έναν σωρό. Εάν χρησιμοποιείτε έναν πίνακα, τα αντικείμενα προστίθενται στο τέλος του πίνακα, ενώ στο δυαδικό δέντρο, τα αντικείμενα προστίθενται από πάνω προς τα κάτω και στη συνέχεια από αριστερά προς τα δεξιά.
• Αφαίρεση (): Αυτή η μέθοδος σάς επιτρέπει να αφαιρέσετε το πρώτο στοιχείο από τη λίστα πινάκων. Καθώς το στοιχείο που μόλις προωθήθηκε δεν είναι πλέον το μεγαλύτερο, η μέθοδος Sift-Down το ωθεί πάντα στη νέα του θέση.
• Κοσκίνισμα (): Αυτή η μέθοδος συγκρίνει ένα αντικείμενο root με τα παιδιά του και στη συνέχεια ωθεί τον μετακινημένο κόμβο στη σωστή του θέση.
• Κοσκινίστε (): Εάν χρησιμοποιήσετε τη μέθοδο πίνακα για να προσθέσετε ένα νεοεισαχθέν στοιχείο σε έναν πίνακα, τότε η μέθοδος Sift-Up βοηθά τον νεοεισαχθέντα κόμβο να μετακινηθεί στη σωστή του θέση. Το νέο στοιχείο συγκρίνεται πρώτα με τον γονικό του κόμβο προσομοιώνοντας τη δομή δεδομένων δέντρου.

  Εφαρμόστε τον τύπο Parent_Index = Child_Index / 2. Συνεχίστε να το κάνετε αυτό μέχρι το μέγιστο στοιχείο να βρίσκεται στην αρχή του πίνακα.

Βασικός Σωρός Operaσεις

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

• Εύρεση – Αναζητήστε ένα αντικείμενο σε ένα σωρό.
• Κύριο θέμα – Προσθέστε ένα νέο παιδί στο σωρό.
• Διαγραφή – Διαγράψτε έναν κόμβο από έναν σωρό.

Δημιουργία Σωρών

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

Ας ξεκινήσουμε λοιπόν να κατασκευάζουμε ένα Min-Heap χρησιμοποιώντας τη μέθοδο του William εισάγοντας τις τιμές 12, 2, 8, 1 και 4. Μπορείτε να δημιουργήσετε το σωρό με n στοιχεία ξεκινώντας με ένα κενό σωρό και στη συνέχεια γεμίζοντάς το διαδοχικά με άλλα στοιχεία χρησιμοποιώντας χρόνο O(n log n).

• Heapify: Μια ρουτίνα εισαγωγής που βοηθά στην εισαγωγή στοιχείων σε ένα σωρό διατηρώντας παράλληλα την ιδιότητα του σωρού.

  Για παράδειγμα, μια λειτουργία max-heapify ελέγχει ότι η τιμή του γονέα είναι μεγαλύτερη από την τιμή του απογόνου του. Τα στοιχεία μπορούν στη συνέχεια να ταξινομηθούν χρησιμοποιώντας μεθόδους όπως η swapping.

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

Επιθεωρήστε τους σωρούς

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

Είναι σημαντικό να ελέγχετε τους σωρούς κατά την ταξινόμηση ή την τοποθέτηση στοιχείων σε ουρά. Ο έλεγχος ότι υπάρχουν στοιχεία προς επεξεργασία χρησιμοποιώντας την Is-Empty() είναι σημαντικός. Το μέγεθος του σωρού θα βοηθήσει στον εντοπισμό των ριζών Max-Heap ή Min-Heap, επομένως πρέπει να γνωρίζετε πόσα στοιχεία ακολουθούν την ιδιότητα heap.

• Μέγεθος – επιστρέφει το μέγεθος ή το μήκος του σωρού. Σας λέει πόσα στοιχεία είναι αποθηκευμένα με ταξινομημένη σειρά.
• Είναι κενό – επιστρέφει TRUE αν ο σωρός είναι null, διαφορετικά επιστρέφει FALSE.

Εδώ, εκτυπώνετε όλα τα στοιχεία στο προτεραιότηταQ βρόχο και, στη συνέχεια, έλεγχος ότι το priorityQ δεν είναι κενό.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Χρήσεις της Δομής Δεδομένων Σωρού

Η δομή δεδομένων σωρού είναι χρήσιμη σε πολλές εφαρμογές προγραμματισμού στην πραγματική ζωή, όπως:

• Βοηθά στο φιλτράρισμα ανεπιθύμητης αλληλογραφίας.
• Υλοποίηση αλγορίθμων γραφημάτων όπως οι Dijkstra και Prim.
• Operaεξισορρόπηση φόρτου συστήματος και συμπίεση δεδομένων.
• Εύρεση στατιστικών στοιχείων τάξης, όπως το k-οστό μικρότερο στοιχείο.
• Υλοποίηση ουρών προτεραιότητας όπου μπορείτε να αναζητήσετε στοιχεία σε μια λίστα σε λογαριθμικό χρόνο.
• Η δομή δεδομένων σωρού χρησιμοποιείται επίσης για την ταξινόμηση μέσω ταξινόμησης σωρού.
• Προσομοίωση πελατών σε ουρά αναμονής.
• Χειρισμός διακοπών στο Operating System.
• Στην κωδικοποίηση Huffman για συμπίεση δεδομένων.
• Ενισχύοντας την αναζήτηση με το καλύτερο πρώτο και τις ευρετικές μεθόδους A* στον σχεδιασμό διαδρομής με τεχνητή νοημοσύνη.

Ιδιότητες ουράς προτεραιότητας σωρού

Οι ακόλουθες ιδιότητες περιγράφουν τον τρόπο συμπεριφοράς της ουράς προτεραιότητας που έχει δημιουργηθεί σε ένα σωρό:

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

Βήματα για την υλοποίηση της ουράς προτεραιότητας σωρού στο Java

Το επόμενο τμήμα κινείται σε ένα σκυρόδεμα Java υλοποίηση που μετατρέπει αυτούς τους κανόνες σε λειτουργικό κώδικα.

Ταξινόμηση σωρών Java μαζί σου, Code Παράδειγμα

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Παραγωγή

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Ταξινόμηση σωρών Python μαζί σου, Code Παράδειγμα

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Παραγωγή

[1, 3, 4, 7, 9]

Στη συνέχεια, θα μάθετε για την Μέθοδος διχοτόμησης.

Συχνές Ερωτήσεις