Δομή δεδομένων σωρού: Τι είναι το Heap; Ελάχιστος & Μέγιστος Σωρός (Παράδειγμα)

Τι είναι το Heap;

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

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

Ακολουθούν οι κύριοι λόγοι για τη χρήση της Δομής Δεδομένων Σωρού:

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

Τύποι Σωρών

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

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

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

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

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

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

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

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

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

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

Μέγιστος σωρός

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

Ακολουθούν μερικές μέθοδοι για την υλοποίηση ενός java max heap

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Βοηθά στο φιλτράρισμα ανεπιθύμητων μηνυμάτων.
Εφαρμογή αλγορίθμων γραφημάτων.
Operating Εξισορρόπηση φορτίου συστήματος και συμπίεση δεδομένων.
Βρείτε τη σειρά στα στατιστικά.
Εφαρμόστε ουρές προτεραιότητας όπου μπορείτε να αναζητήσετε στοιχεία σε μια λίστα σε λογαριθμικό χρόνο.
Η δομή δεδομένων σωρού χρησιμοποιείται επίσης για ταξινόμηση.
Προσομοίωση πελατών σε μια γραμμή.
Διακοπή χειρισμού Operating System.
Στην κωδικοποίηση του Huffman για συμπίεση δεδομένων.

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

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

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

Ταξινόμηση σωρών σε JAVA με Παράδειγμα κώδικα

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 the root and the largest element 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 με Παράδειγμα Κώδικα

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)