Κατανοήστε πώς να εφαρμόσετε ένα δυαδικό σωρό στην Java



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

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

Εδώ είναι η ατζέντα για αυτό το άρθρο:





  1. Τι είναι το είδος σωρού;
  2. Μέγιστος σωρός
  3. Ελάχιστο σωρό
  4. Εφαρμογή σωρού στην Java
    • Διάγραμμα
    • Κώδικας

Ας ξεκινήσουμε!

Τι είναι το είδος σωρού;

Ο σωρός είναι βασικά μια δομή δεδομένων που βασίζεται σε δέντρο. Έχει κόμβους. Ο κόμβος περιλαμβάνει ορισμένα στοιχεία. Κάθε κόμβος περιέχει ένα στοιχείο.



Οι κόμβοι μπορεί να έχουν παιδιά. Εάν δεν υπάρχουν παιδιά, ονομάζεται Φύλλο.

Υπάρχουν δύο κανόνες που πρέπει να ακολουθούνται:

  • Η τιμή κάθε κόμβου πρέπει να είναι μικρότερη ή ίση με όλες τις τιμές που είναι αποθηκευμένες στα παιδιά του.
  • Έχει το λιγότερο δυνατό ύψος.

Οι σωροί είναι εξαιρετικά αποτελεσματικοί στην εξαγωγή τουλιγότερο ή μεγαλύτερο στοιχείο.



Ας προχωρήσουμε στο ελάχιστο σωρό τώρα!

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

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

Αναπαράσταση του ελάχιστου σωρού

Arr [(i-1) / 2]: Αυτό θα επιστρέψει τον γονικό κόμβο.

Arr [(2 * i) + 1]: Αυτό θα επιστρέψει τον αριστερό θυγατρικό κόμβο.

Arr [(2 * i) + 2]: Αυτό θα επιστρέψει τον σωστό θυγατρικό κόμβο.

Υπάρχουν ορισμένες μέθοδοι του Min Heap:

  • εισάγετε(): Προστίθεται ένα νέο κλειδί στο τέλος του δέντρου. Σε περίπτωση που το νέο κλειδί είναι μεγαλύτερο από τον γονέα, τότε δεν χρειάζεται να κάνουμε τίποτα, αλλιώς, πρέπει να διασχίσουμε για να δημιουργήσουμε την ιδιότητα σωρού.
  • getMin (): Αυτές οι μέθοδοι βοηθούν στην επιστροφή του ριζικού στοιχείου.
  • εκχύλισμα Min (): αυτή η μέθοδος επιστρέφει το ελάχιστοστοιχείο.

Προχωρώντας στο σωρό Max τώρα.

αριθμοί fibonacci c ++

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

Το Max heap είναι ένα πλήρες δυαδικό δέντρο στο οποίο η τιμή του ριζικού στοιχείου είναι μεγαλύτερη ή ίση με οποιοδήποτε από τα θυγατρικά στοιχεία.

Το Max heap αποτελείται και από πολλές μεθόδους!

  • Εισάγετε (): θα εισαγάγει ένα στοιχείο στο σωρό.
  • Διαγράφω() : θα διαγράψει ένα στοιχείο από το σωρό.
  • FindMax (): θα βρει το μέγιστο στοιχείο από το σωρό.
  • printHeap (): Θα εκτυπώσει το περιεχόμενο του σωρού

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

Εφαρμογή σωρού στην Java

Διάγραμμα:

Heap

Το παραπάνω διάγραμμα δείχνει το δυαδικό σωρό στην Java. Όπως έχετε μάθει ότι υπάρχουν δύο σωροί: Ελάχιστος σωρός και Μέγιστος σωρός, εδώ είναι ένα διάγραμμα:

Τώρα, προχωρώντας στο επόμενο τμήμα μας, θα δούμε πώς να εφαρμόσουμε ένα δυαδικό σωρό στην Java.

Κώδικας:

δημόσια τάξη BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Αυτό θα προετοιμάσει το σωρό μας με το προεπιλεγμένο μέγεθος. * / public BinaryHeap (χωρητικότητα int) {heapSize = 0 heap = new int [χωρητικότητα + 1] Arrays.fill (heap, -1)} / ** * Αυτό θα ελέγξει εάν ο σωρός είναι κενός ή όχι * Πολυπλοκότητα: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Αυτό θα ελέγξει εάν ο σωρός είναι πλήρης ή όχι * Πολυπλοκότητα: O (1) * / public boolean isFull () {return heapSize == heap .length} ιδιωτικό int γονέα (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Αυτό θα εισαγάγει νέο στοιχείο στο σωρό * Πολυπλοκότητα: O (log N) * Ως χειρότερο σενάριο, πρέπει να περάσουμε μέχρι το root * / public void insert (int x) {if (isFull ()) ρίξτε νέο NoSuchElementException ('Ο σωρός είναι πλήρης, Χωρίς χώρο για εισαγωγή νέο στοιχείο ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Αυτό θα διαγράψει το στοιχείο στο ευρετήριο x * Πολυπλοκότητα: O (log N) * * / public int delete (int x) {if (isEmpty ()) ρίξτε νέο NoSuchElementException ('Το σωρό είναι κενό, Χωρίς στοιχείο για διαγραφή') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Αυτή η μέθοδος χρησιμοποιήθηκε για τη συντήρηση της ιδιότητας σωρού κατά την εισαγωγή ενός στοιχείου. * * / private void heapifyUp (int i) {int temp = heap [i] ενώ (i> 0 && temp> heap [γονέας (i)]) {heap [i] = heap [γονέας (i)] i = γονέας (i)} σωρός [i] = temp} / ** * Αυτή η μέθοδος χρησιμοποιήθηκε για τη συντήρηση της ιδιότητας σωρού κατά τη διαγραφή ενός στοιχείου. * * / private void heapifyDown (int i) {int child int temp = heap [i] ενώ (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Αυτή η μέθοδος χρησιμοποιήθηκε για την εκτύπωση όλων των στοιχείων του σωρού * * / public void printHeap () {System.out.print ('nHeap =') για (int i = 0 i

Με αυτό, καταλήγουμε στο τέλος αυτού του άρθρου σχετικά με το Binary Heap στην Java. Δείτε το από την Edureka, μια αξιόπιστη διαδικτυακή εταιρεία εκμάθησης με δίκτυο περισσότερων από 250.000 ικανοποιημένων μαθητών σε όλο τον κόσμο. Το μάθημα εκπαίδευσης και πιστοποίησης Java J2EE και SOA της Edureka έχει σχεδιαστεί για φοιτητές και επαγγελματίες που θέλουν να γίνουν προγραμματιστές Java. Το μάθημα έχει σχεδιαστεί για να σας δώσει μια πρώτη αρχή στον προγραμματισμό Java και να σας εκπαιδεύσει τόσο για τις βασικές όσο και για τις προηγμένες ιδέες Java μαζί με διάφορα πλαίσια Java όπως το Hibernate & Spring.

Έχετε μια ερώτηση για εμάς; Παρακαλώ αναφέρετέ το στην ενότητα σχολίων αυτού του ιστολογίου 'Java ArrayList' και θα επικοινωνήσουμε μαζί σας το συντομότερο δυνατό.