Μενού

Τι είναι μια δομή δεδομένων σωρού στην Java

what is heap data structure java

Δοκιμάστε Το Όργανο Μας Για Την Εξάλειψη Των Προβλημάτων

Αυτό το σεμινάριο εξηγεί τι είναι η δομή δεδομένων Java Heap και σχετικές έννοιες όπως Min Heap, Max Heap, Heap Sort, Stack vs Heap με παραδείγματα:

Ένας σωρός είναι μια ειδική δομή δεδομένων στην Java. Ένας σωρός είναι μια δομή δεδομένων που βασίζεται σε δέντρο και μπορεί να ταξινομηθεί ως πλήρης δυαδική δέντρα. Όλοι οι κόμβοι του σωρού είναι διατεταγμένοι με συγκεκριμένη σειρά.

=> Επισκεφτείτε εδώ για να δείτε τη σειρά εκπαίδευσης Java για όλους

Δομή δεδομένων σωρού

Τι θα μάθετε:

Δομή δεδομένων σωρού στην Java

Στη δομή δεδομένων σωρού, ο ριζικός κόμβος συγκρίνεται με τα παιδιά του και τακτοποιείται σύμφωνα με τη σειρά. Έτσι, αν το a είναι ριζικός κόμβος και το b είναι το παιδί του, τότε η ιδιότητα, κλειδί (a)> = κλειδί (b) θα δημιουργήσει ένα μέγιστο σωρό.

Η παραπάνω σχέση μεταξύ της ρίζας και του θυγατρικού κόμβου ονομάζεται 'Heap Property'.

Ανάλογα με τη σειρά των κόμβων γονέα-παιδιού, ο σωρός είναι γενικά δύο τύπων:

# 1) Max-Heap :Σε ένα Max-Heap, το κλειδί κόμβου ρίζας είναι το μεγαλύτερο από όλα τα πλήκτρα στο σωρό. Πρέπει να διασφαλιστεί ότι η ίδια ιδιότητα ισχύει για όλα τα υποδέντρα στο σωρό αναδρομικά.

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

Δείγμα Max-Heap

# 2) Ελάχιστο σωρό :Στην περίπτωση ενός Min-Heap, το κλειδί ριζικού κόμβου είναι το μικρότερο ή ελάχιστο μεταξύ όλων των άλλων κλειδιών που υπάρχουν στο σωρό. Όπως στο Max heap, αυτή η ιδιότητα θα πρέπει να ισχύει αναδρομικά σε όλα τα άλλα υποδέντρα στο σωρό.

Ενα παράδειγμα, ενός δέντρου Min-heap, φαίνεται παρακάτω. Όπως μπορούμε να δούμε, το βασικό κλειδί είναι το μικρότερο από όλα τα άλλα κλειδιά στο σωρό.

Ελάχιστο δέντρο

Μια δομή δεδομένων σωρού μπορεί να χρησιμοποιηθεί στους ακόλουθους τομείς:

  • Οι σωροί χρησιμοποιούνται κυρίως για την εφαρμογή ουρών προτεραιότητας.
  • Ειδικά το min-heap μπορεί να χρησιμοποιηθεί για τον προσδιορισμό των μικρότερων διαδρομών μεταξύ των κορυφών σε ένα γράφημα.

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

Δυαδικός σωρός

Ένας δυαδικός σωρός πληροί τις παρακάτω ιδιότητες:

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

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

Έτσι, γενικά για οποιοδήποτε iουκόμβος στην αναπαράσταση δυαδικών συστοιχιών σωρού, A (i), μπορούμε να αντιπροσωπεύσουμε τους δείκτες άλλων κόμβων όπως φαίνεται παρακάτω.

Α ((i-1) / 2)Αντιπροσωπεύει τον γονικό κόμβο
Η πρόσβαση είναι ταχύτερη.Αργότερα από τη στοίβα.
A ((2 * i) +1)Αντιπροσωπεύει τον αριστερό θυγατρικό κόμβο
A ((2 * i) +2)Αντιπροσωπεύει τον σωστό θυγατρικό κόμβο

Εξετάστε τον ακόλουθο δυαδικό σωρό:

δυαδικός σωρός

Η παράσταση του πίνακα του παραπάνω ελάχιστου δυαδικού σωρού έχει ως εξής:

παράσταση πίνακα - Ελάχιστο δυαδικό σωρό

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

Στη συνέχεια, θα εφαρμόσουμε το δυαδικό σωρό στην Java.

Το παρακάτω πρόγραμμα δείχνει το δυαδικό σωρό στην Java.

import java.util.*; class BinaryHeap { private static final int d= 2; private int() heap; private int heapSize; //BinaryHeap constructor with default size public BinaryHeap(int capacity){ heapSize = 0; heap = new int( capacity+1); Arrays.fill(heap, -1); } //is heap empty? public boolean isEmpty(){ return heapSize==0; } //is heap full? public boolean isFull(){ return heapSize == heap.length; } //return parent private int parent(int i){ return (i-1)/d; } //return kth child private int kthChild(int i,int k){ return d*i +k; } //insert new element into the heap public void insert(int x){ if(isFull()) throw new NoSuchElementException('Heap is full, No space to insert new element'); heap(heapSize++) = x; heapifyUp(heapSize-1); } //delete an element from the heap at given position public int delete(int x){ if(isEmpty()) throw new NoSuchElementException('Heap is empty, No element to delete'); int key = heap(x); heap(x) = heap(heapSize -1); heapSize--; heapifyDown(x); return key; } //maintain heap property during insertion private void heapifyUp(int i) { int temp = heap(i); while(i>0 && temp > heap(parent(i))){ heap(i) = heap(parent(i)); i = parent(i); } heap(i) = temp; } //maintain heap property during deletion private void heapifyDown(int i){ int child; int temp = heap(i); while(kthChild(i, 1) heap(rightChild)?leftChild:rightChild; } //print the heap public void printHeap() { System.out.print('nHeap = '); for (int i = 0; i

Παραγωγή:

nHeap = 7 4 6 1 3 2 5

Ελάχιστο σωρό στην Ιάβα

Ένα ελάχιστο σωρό στην Java είναι ένα πλήρες δυαδικό δέντρο. Στο min-heap, ο ριζικός κόμβος είναι μικρότερος από όλους τους άλλους κόμβους στο σωρό. Γενικά, η τιμή κλειδιού κάθε εσωτερικού κόμβου είναι μικρότερη ή ίση με τους θυγατρικούς κόμβους του.

Όσον αφορά την αναπαράσταση συστοιχίας του min-heap, εάν ένας κόμβος αποθηκεύεται στη θέση «i», τότε ο αριστερός θυγατρικός κόμβος του αποθηκεύεται στη θέση 2i + 1 και στη συνέχεια ο δεξί θυγατρικός κόμβος βρίσκεται στη θέση 2i + 2. Η θέση (i-1) / 2 επιστρέφει τον γονικό κόμβο της.

Παρατίθενται παρακάτω οι διάφορες λειτουργίες που υποστηρίζονται από το min-heap.

# 1) Εισαγωγή (): Αρχικά, ένα νέο κλειδί προστίθεται στο τέλος του δέντρου. Εάν το κλειδί είναι μεγαλύτερο από τον μητρικό κόμβο του, διατηρείται η ιδιότητα σωρού. Διαφορετικά, πρέπει να διασχίσουμε το κλειδί προς τα πάνω για να εκπληρώσουμε το σωρό. Η λειτουργία εισαγωγής σε ελάχιστο σωρό απαιτεί χρόνο O (log n).

# 2) απόσπασμα Min (): Αυτή η λειτουργία αφαιρεί το ελάχιστο στοιχείο από το σωρό. Σημειώστε ότι η ιδιότητα σωρού θα πρέπει να διατηρηθεί μετά την αφαίρεση του ριζικού στοιχείου (min στοιχείο) από το σωρό. Όλη αυτή η λειτουργία παίρνει O (Logn).

# 3) getMin (): Το getMin () επιστρέφει τη ρίζα του σωρού που είναι επίσης το ελάχιστο στοιχείο. Αυτή η λειτουργία γίνεται σε χρόνο O (1).

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

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

Το παραπάνω διάγραμμα δείχνει ένα δέντρο με ελάχιστο σωρό. Βλέπουμε ότι η ρίζα του δέντρου είναι το ελάχιστο στοιχείο στο δέντρο. Δεδομένου ότι η ρίζα βρίσκεται στην τοποθεσία 0, το αριστερό του παιδί τοποθετείται στο 2 * 0 + 1 = 1 και το δεξί παιδί στο 2 * 0 + 2 = 2.

Αλγόριθμος ελάχιστου σωρού

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

procedure build_minheap Array Arr: of size N => array of elements { repeat for (i = N/2 ; i >= 1 ; i--) call procedure min_heapify (A, i); } procedure min_heapify (var A( ) , var i, var N) { var left = 2*i; var right = 2*i+1; var smallest; if(left <= N and A(left) < A( i ) ) smallest = left; else smallest = i; if(right <= N and A(right) < A(smallest) ) smallest = right; if(smallest != i) { swap A( i ) and A( smallest )); call min_heapify (A, smallest,N); } }

Εφαρμογή ελάχιστου σωρού στην Java

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

Το ακόλουθο πρόγραμμα Java εφαρμόζει το min-heap χρησιμοποιώντας Arrays. Εδώ χρησιμοποιούμε παράσταση συστοιχίας για σωρό και στη συνέχεια εφαρμόζουμε τη συνάρτηση heapify για να διατηρήσουμε την ιδιότητα σωρού κάθε στοιχείου που προστίθεται στο σωρό. Τέλος, εμφανίζουμε το σωρό.

class Min_Heap { private int() HeapArray; private int size; private int maxsize; private static final int FRONT = 1; //constructor to initialize the HeapArray public Min_Heap(int maxsize) { this.maxsize = maxsize; this.size = 0; HeapArray = new int(this.maxsize + 1); HeapArray(0) = Integer.MIN_VALUE; } // returns parent position for the node private int parent(int pos) { return pos / 2; } // returns the position of left child private int leftChild(int pos) { return (2 * pos); } // returns the position of right child private int rightChild(int pos) { return (2 * pos) + 1; } // checks if the node is a leaf node private boolean isLeaf(int pos) { if (pos >= (size / 2) && pos HeapArray(leftChild(pos)) || HeapArray(pos) > HeapArray(rightChild(pos))) { // swap with left child and then heapify the left child if (HeapArray(leftChild(pos)) = maxsize) { return; } HeapArray(++size) = element; int current = size; while (HeapArray(current) = 1; pos--) { minHeapify(pos); } } // remove and return the heap elment public int remove() { int popped = HeapArray(FRONT); HeapArray(FRONT) = HeapArray(size--); minHeapify(FRONT); return popped; } } class Main{ public static void main(String() arg) { //construct a min heap from given data System.out.println('The Min Heap is '); Min_Heap minHeap = new Min_Heap(7); minHeap.insert(12); minHeap.insert(15); minHeap.insert(30); minHeap.insert(40); minHeap.insert(50); minHeap.insert(90); minHeap.insert(45); minHeap.minHeap(); //display the min heap contents minHeap.display(); //display root node of the min heap System.out.println('The Min val(root node):' + minHeap.remove()); } }

Παραγωγή:

Εφαρμογή ελάχιστου σωρού στην Java

Μέγιστος σωρός στην Ιάβα

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

Ενώ ο μέγιστος σωρός αντιστοιχίζεται σε έναν πίνακα, εάν οποιοσδήποτε κόμβος αποθηκεύεται στη θέση «i», τότε το αριστερό του παιδί αποθηκεύεται στο 2i +1 και το δεξί παιδί αποθηκεύεται στο 2i + 2.

Το τυπικό Max-heap θα φαίνεται όπως φαίνεται παρακάτω:

Μέγιστος σωρός στην Ιάβα

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

Παρόμοια με το min-heap, ο μέγιστος σωρός μπορεί επίσης να αναπαρασταθεί ως πίνακας.

Αν λοιπόν το A είναι ένας πίνακας που αντιπροσωπεύει το Max heap τότε το A (0) είναι ο ριζικός κόμβος. Ομοίως, εάν το A (i) είναι οποιοσδήποτε κόμβος στο μέγιστο σωρό, τότε τα ακόλουθα είναι οι άλλοι γειτονικοί κόμβοι που μπορούν να αναπαρασταθούν χρησιμοποιώντας έναν πίνακα.

  • Το ((i-1) / 2) αντιπροσωπεύει τον γονικό κόμβο του A (i).
  • Το A ((2i +1)) αντιπροσωπεύει τον αριστερό θυγατρικό κόμβο του A (i).
  • Το (2i + 2) επιστρέφει τον σωστό θυγατρικό κόμβο του A (i).

Οι λειτουργίες που μπορούν να εκτελεστούν στο Max Heap δίνονται παρακάτω.

# 1) Εισαγωγή: Εισαγωγή λειτουργίας εισάγει μια νέα τιμή στο μέγιστο δέντρο σωρού. Εισάγεται στο τέλος του δέντρου. Εάν το νέο κλειδί (τιμή) είναι μικρότερο από τον μητρικό κόμβο του, διατηρείται η ιδιότητα σωρού. Διαφορετικά, το δέντρο πρέπει να είναι γεμάτο για να διατηρήσει την ιδιότητα του σωρού.

μετατρέψτε το βίντεο youtube σε mp4 δωρεάν

Η χρονική πολυπλοκότητα της λειτουργίας εισαγωγής είναι O (log n).

# 2) ExtractMax: Η λειτουργία ExtractMax αφαιρεί το μέγιστο στοιχείο (root) από το μέγιστο σωρό. Η λειτουργία συσσωρεύει επίσης το μέγιστο σωρό για να διατηρήσει την ιδιότητα σωρού. Η χρονική πολυπλοκότητα αυτής της λειτουργίας είναι O (log n).

# 3) getMax: Η λειτουργία getMax επιστρέφει τον ριζικό κόμβο του μέγιστου σωρού με την πολυπλοκότητα χρόνου του O (1).

Το παρακάτω πρόγραμμα Java εφαρμόζει το μέγιστο σωρό. Χρησιμοποιούμε το ArrayList εδώ για να αντιπροσωπεύσουμε τα μέγιστα στοιχεία σωρού.

import java.util.ArrayList; class Heap { void heapify(ArrayList hT, int i) { int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT.get(largest)) largest = l; if (r hT.get(largest)) largest = r; if (largest != i) { int temp = hT.get(largest); hT.set(largest, hT.get(i)); hT.set(i, temp); heapify(hT, largest); } } void insert(ArrayList hT, int newNum) { int size = hT.size(); if (size == 0) { hT.add(newNum); } else { hT.add(newNum); for (int i = size / 2 - 1; i >= 0; i--) { heapify(hT, i); } } } void deleteNode(ArrayList hT, int num) { int size = hT.size(); int i; for (i = 0; i = 0; j--) { heapify(hT, j); } } void printArray(ArrayList array, int size) { for (Integer i : array) { System.out.print(i + ' '); } System.out.println(); } } class Main{ public static void main(String args()) { ArrayList array = new ArrayList(); int size = array.size(); Heap h = new Heap(); h.insert(array, 3); h.insert(array, 4); h.insert(array, 9); h.insert(array, 5); h.insert(array, 2); System.out.println('Max-Heap array: '); h.printArray(array, size); h.deleteNode(array, 4); System.out.println('After deleting an element: '); h.printArray(array, size); } }

Παραγωγή:

OUTPUT - Μέγιστος σωρός στην Java

Ελάχιστο σωρό ουράς προτεραιότητας στην Ιάβα

Η δομή δεδομένων ουράς προτεραιότητας στην Java μπορεί να χρησιμοποιηθεί άμεσα για την αναπαράσταση του min-heap. Από προεπιλογή, η ουρά προτεραιότητας εφαρμόζει ελάχιστο σωρό.

Το παρακάτω πρόγραμμα δείχνει το ελάχιστο σωρό στην Java χρησιμοποιώντας την ουρά προτεραιότητας.

import java.util.*; class Main { public static void main(String args()) { // Create priority queue object PriorityQueue pQueue_heap = new PriorityQueue(); // Add elements to the pQueue_heap using add() pQueue_heap.add(100); pQueue_heap.add(30); pQueue_heap.add(20); pQueue_heap.add(40); // Print the head (root node of min heap) using peek method System.out.println('Head (root node of min heap):' + pQueue_heap.peek()); // Print min heap represented using PriorityQueue System.out.println(' Min heap as a PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // remove head (root of min heap) using poll method pQueue_heap.poll(); System.out.println(' Min heap after removing root node:'); //print the min heap again Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }

Παραγωγή:

OUTPUT - Ελάχιστος σωρός ουράς προτεραιότητας στην Java

Μέγιστος σωρός ουράς προτεραιότητας στην Ιάβα

Για να αντιπροσωπεύσουμε το μέγιστο σωρό στην Java χρησιμοποιώντας την ουρά προτεραιότητας, πρέπει να χρησιμοποιήσουμε το Collections.reverseOrder για να αντιστρέψουμε το ελάχιστο σωρό. Η ουρά προτεραιότητας αντιπροσωπεύει άμεσα ένα ελάχιστο σωρό στην Java.

Έχουμε εφαρμόσει το Max Heap χρησιμοποιώντας μια ουρά προτεραιότητας στο παρακάτω πρόγραμμα.

import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue //with Collections.reverseOrder to represent max heap PriorityQueue pQueue_heap = new PriorityQueue(Collections.reverseOrder()); // Add items to the pQueue using add() pQueue_heap.add(10); pQueue_heap.add(90); pQueue_heap.add(20); pQueue_heap.add(40); // Printing all elements of max heap System.out.println('The max heap represented as PriorityQueue:'); Iterator iter = pQueue_heap.iterator(); while (iter.hasNext()) System.out.print(iter.next() + ' '); // Print the highest priority element (root of max heap) System.out.println(' Head value (root node of max heap):' + pQueue_heap.peek()); // remove head (root node of max heap) with poll method pQueue_heap.poll(); //print the max heap again System.out.println(' Max heap after removing root: '); Iterator iter2 = pQueue_heap.iterator(); while (iter2.hasNext()) System.out.print(iter2.next() + ' '); } }

Παραγωγή:

Ουρά προτεραιότητας Max Heap

Ταξινόμηση σωρού στην Ιάβα

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

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

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

  • Δημιουργήστε έναν σωρό από τον δεδομένο πίνακα.
  • Αφαιρέστε επανειλημμένα το ριζικό στοιχείο από το σωρό και μετακινήστε το στον ταξινομημένο πίνακα. Σώστε τον υπόλοιπο σωρό.

Ο χρόνος πολυπλοκότητας του είδους Heap είναι O (n log n) σε όλες τις περιπτώσεις. Η πολυπλοκότητα του διαστήματος είναι O (1).

Αλγόριθμος Heap Sort In Java

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

# 1) Αλγόριθμος Heap Sort για ταξινόμηση με αύξουσα σειρά:

  • Δημιουργήστε έναν μέγιστο σωρό για τη συγκεκριμένη σειρά που θα ταξινομηθεί.
  • Διαγράψτε τη ρίζα (μέγιστη τιμή στον πίνακα εισαγωγής) και μετακινήστε την στον ταξινομημένο πίνακα. Τοποθετήστε το τελευταίο στοιχείο στον πίνακα στη ρίζα.
  • Θεραπεύστε τη νέα ρίζα του σωρού.
  • Επαναλάβετε τα βήματα 1 και 2 έως ότου ταξινομηθεί ολόκληρος ο πίνακας.

# 2) Αλγόριθμος Heap Sort για ταξινόμηση με φθίνουσα σειρά:

  • Κατασκευάστε ένα ελάχιστο σωρό για τον δεδομένο πίνακα.
  • Αφαιρέστε τη ρίζα (ελάχιστη τιμή στον πίνακα) και αλλάξτε την με το τελευταίο στοιχείο του πίνακα.
  • Θεραπεύστε τη νέα ρίζα του σωρού.
  • Επαναλάβετε τα βήματα 1 και 2 έως ότου ταξινομηθεί ολόκληρος ο πίνακας.

Εφαρμογή Heap Sort στην Java

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

import java.util.*; class HeapSort{ public void heap_sort(int heap_Array()) { int heap_len = heap_Array.length; // construct max heap for (int i = heap_len / 2 - 1; i >= 0; i--) { heapify(heap_Array, heap_len, i); } // Heap sort for (int i = heap_len - 1; i >= 0; i--) { int temp = heap_Array(0); heap_Array(0) = heap_Array(i); heap_Array(i) = temp; // Heapify root element heapify(heap_Array, i, 0); } } void heapify(int heap_Array(), int n, int i) { // find largest value int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left heap_Array(largest)) largest = left; if (right heap_Array(largest)) largest = right; // recursively heapify and swap if root is not the largest if (largest != i) { int swap = heap_Array(i); heap_Array(i) = heap_Array(largest); heap_Array(largest) = swap; heapify(heap_Array, n, largest); } } } class Main{ public static void main(String args()) { //define input array and print it int heap_Array() = {6,2,9,4,10,15,1,13}; System.out.println('Input Array:' + Arrays.toString(heap_Array)); //call HeapSort method for given array HeapSort hs = new HeapSort(); hs.heap_sort(heap_Array); //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(heap_Array)); } }

Παραγωγή:

έξοδος - Εφαρμογή Heap Sort στην Java

Η συνολική χρονική πολυπλοκότητα της τεχνικής ταξινόμησης σωρού είναι O (nlogn). Η χρονική πολυπλοκότητα της τεχνικής heapify είναι O (logn). Ενώ η χρονική πολυπλοκότητα της κατασκευής του σωρού είναι O (n).

Στοίβα εναντίον σωρού στην Ιάβα

Ας δούμε τώρα μερικές από τις διαφορές μεταξύ της δομής δεδομένων Stack και του σωρού.

ΣωρόςΣωρός
Μια στοίβα είναι μια γραμμική δομή δεδομένων.Ένας σωρός είναι μια ιεραρχική δομή δεδομένων.
Ακολουθεί την παραγγελία LIFO (Last In, First Out).Το Traversal είναι σε επίπεδο επίπεδο.
Χρησιμοποιείται κυρίως για κατανομή στατικής μνήμης.Χρησιμοποιείται για δυναμική κατανομή μνήμης.
Η μνήμη κατανέμεται διαδοχικά.Η μνήμη κατανέμεται σε τυχαίες τοποθεσίες.
Το μέγεθος στοίβας περιορίζεται σύμφωνα με το λειτουργικό σύστημα.Δεν επιβάλλεται όριο στο μέγεθος του σωρού από το λειτουργικό σύστημα.
Το Stack έχει πρόσβαση μόνο σε τοπικές μεταβλητές.Ο σωρός έχει καθολικές μεταβλητές που του έχουν ανατεθεί.
Η κατανομή / αφαίρεση της μνήμης είναι αυτόματη.Η κατανομή / απενεργοποίηση πρέπει να γίνει χειροκίνητα από τον προγραμματιστή.
Η στοίβα μπορεί να υλοποιηθεί χρησιμοποιώντας Arrays, Linked List, ArrayList κ.λπ. ή οποιαδήποτε άλλη γραμμική δομή δεδομένων.Ο σωρός υλοποιείται χρησιμοποιώντας πίνακες ή δέντρα.
Κόστος συντήρησης εάν είναι μικρότερο.Πιο δαπανηρή συντήρηση.
Μπορεί να οδηγήσει σε έλλειψη μνήμης καθώς η μνήμη είναι περιορισμένη.Χωρίς έλλειψη μνήμης, αλλά μπορεί να υποφέρει από κατακερματισμό της μνήμης.

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

Q # 1) Είναι στοίβα γρηγορότερη από το Heap;

Απάντηση: Μια στοίβα είναι ταχύτερη από το σωρό, καθώς η πρόσβαση είναι γραμμική στη στοίβα σε σύγκριση με το σωρό.

Q # 2) Σε τι χρησιμοποιείται ένας σωρός;

Απάντηση: Ο σωρός χρησιμοποιείται κυρίως σε αλγόριθμους που βρίσκουν την ελάχιστη ή συντομότερη διαδρομή μεταξύ δύο σημείων, όπως ο αλγόριθμος Dijkstra, για ταξινόμηση χρησιμοποιώντας ταξινόμηση σωρού, για υλοποιήσεις ουράς προτεραιότητας (min-heap) κ.λπ.

Q # 3) Τι είναι ένας σωρός; Ποιοι είναι οι τύποι του;

Απάντηση: Ένας σωρός είναι μια ιεραρχική δομή δεδομένων που βασίζεται σε δέντρα. Ένας σωρός είναι ένα πλήρες δυαδικό δέντρο. Οι σωροί είναι δύο τύπων, δηλαδή ο μέγιστος σωρός στον οποίο ο ριζικός κόμβος είναι ο μεγαλύτερος μεταξύ όλων των κόμβων. Ελάχιστο σωρό στον οποίο ο ριζικός κόμβος είναι ο μικρότερος ή ελάχιστος μεταξύ όλων των πλήκτρων.

Q # 4) Ποια είναι τα πλεονεκτήματα του Heap έναντι ενός stack;

Απάντηση: Το κύριο πλεονέκτημα της στοίβας over heap είναι στο σωρό, η μνήμη κατανέμεται δυναμικά και ως εκ τούτου δεν υπάρχει όριο στο πόση μνήμη μπορεί να χρησιμοποιηθεί. Δεύτερον, μόνο τοπικές μεταβλητές μπορούν να εκχωρηθούν στη στοίβα, ενώ μπορούμε επίσης να εκχωρήσουμε καθολικές μεταβλητές στο σωρό.

Ε # 5) Μπορεί ο σωρός να έχει διπλότυπα;

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

συμπέρασμα

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

=> Ανατρέξτε στον τέλειο οδηγό εκπαίδευσης Java εδώ.

Συνιστώμενη ανάγνωση

^