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

Πίνακας περιεχομένων

Λειτουργίες σωρού
Παραδείγματα Python, Java, C / C ++
Εφαρμογές δομής δεδομένων σωρού

Σε αυτό το σεμινάριο, θα μάθετε τι είναι η δομή δεδομένων σωρού. Επίσης, θα βρείτε λειτουργικά παραδείγματα λειτουργιών σωρού σε C, C ++, Java και Python.

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

Ένα πλήρες δυαδικό δέντρο είναι ένα ειδικό δυαδικό δέντρο στο οποίο

κάθε επίπεδο, εκτός από το τελευταίο, είναι γεμάτο
όλοι οι κόμβοι είναι όσο το δυνατόν πιο αριστερά

Η ιδιότητα Heap είναι η ιδιοκτησία ενός κόμβου στον οποίο

(για μέγιστο σωρό) το κλειδί κάθε κόμβου είναι πάντα μεγαλύτερο από τον θυγατρικό κόμβο του και το κλειδί του ριζικού κόμβου είναι το μεγαλύτερο μεταξύ όλων των άλλων κόμβων.
(για ελάχιστο σωρό) το κλειδί κάθε κόμβου είναι πάντα μικρότερο από τον θυγατρικό κόμβο / δευτερόλεπτο και το κλειδί του ριζικού κόμβου είναι το μικρότερο μεταξύ όλων των άλλων κόμβων.

Λειτουργίες σωρού

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

Θεραπεύστε

Το Heapify είναι η διαδικασία δημιουργίας μιας δομής δεδομένων σωρού από ένα δυαδικό δέντρο. Χρησιμοποιείται για τη δημιουργία ενός Min-Heap ή ενός Max-Heap.

Αφήστε τον πίνακα εισαγωγής να είναι
Δημιουργήστε ένα πλήρες δυαδικό δέντρο από τον πίνακα
Ξεκινήστε από τον πρώτο δείκτη κόμβου χωρίς φύλλα του οποίου ο δείκτης δίνεται από n/2 - 1.
Ορίστε το τρέχον στοιχείο iως largest.
Ο δείκτης αριστερού παιδιού δίνεται από 2i + 1και το δεξί παιδί δίνεται από 2i + 2.
Εάν leftChildείναι μεγαλύτερο από currentElement(δηλαδή στοιχείο στο ithευρετήριο), ορίστε leftChildIndexως μεγαλύτερο.
Εάν rightChildείναι μεγαλύτερο από το στοιχείο στο largest, ορίστε rightChildIndexως largest.
Ανταλλάξτε largestμεcurrentElement
Επαναλάβετε τα βήματα 3-7 έως ότου τα δευτερεύοντα δέντρα αδρανοποιηθούν επίσης.

Αλγόριθμος

 Heapify(array, size, i) set i as largest leftChild = 2i + 1 rightChild = 2i + 2 if leftChild > array(largest) set leftChildIndex as largest if rightChild > array(largest) set rightChildIndex as largest swap array(i) and array(largest)

Για να δημιουργήσετε ένα Max-Heap:

 MaxHeap(array, size) loop from the first index of non-leaf node down to zero call heapify

Για το Min-Heap, leftChildκαι τα δύο και rightChildπρέπει να είναι μικρότερα από το γονικό για όλους τους κόμβους.

Εισαγωγή στοιχείου στο σωρό

Αλγόριθμος για εισαγωγή στο Max Heap

 If there is no node, create a newNode. else (a node is already present) insert the newNode at the end (last node from left to right.) heapify the array

Εισαγάγετε το νέο στοιχείο στο τέλος του δέντρου.
Σώστε το δέντρο.

Για το Min Heap, ο παραπάνω αλγόριθμος τροποποιείται έτσι ώστε να parentNodeείναι πάντα μικρότερος από newNode.

Διαγραφή στοιχείου από το σωρό

Αλγόριθμος για διαγραφή στο Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array

Επιλέξτε το στοιχείο που θα διαγραφεί.
Ανταλλάξτε το με το τελευταίο στοιχείο.
Αφαιρέστε το τελευταίο στοιχείο.
Σώστε το δέντρο.

Για το Min Heap, ο παραπάνω αλγόριθμος τροποποιείται έτσι ώστε και τα δύο να childNodesείναι μεγαλύτερα μικρότερα από currentNode.

Ρίξτε μια ματιά (Εύρεση μέγ. / Λεπτό)

Η λειτουργία Peek επιστρέφει το μέγιστο στοιχείο από το Max Heap ή το ελάχιστο στοιχείο από το Min Heap χωρίς να διαγραφεί ο κόμβος.

Και για το Max heap και το Min Heap

 επιστροφή rootNode

Απόσπασμα-Μέγ. / Ελάχ

Το Extract-Max επιστρέφει τον κόμβο με τη μέγιστη τιμή μετά την αφαίρεσή του από ένα Max Heap ενώ το Extract-Min επιστρέφει τον κόμβο με το ελάχιστο μετά την αφαίρεσή του από το Min Heap.

Παραδείγματα Python, Java, C / C ++

Python Java C C ++

 # Max-Heap data structure in Python def heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr(i) < arr(l): largest = l if r < n and arr(largest) < arr(r): largest = r if largest != i: arr(i),arr(largest) = arr(largest),arr(i) heapify(arr, n, largest) def insert(array, newNum): size = len(array) if size == 0: array.append(newNum) else: array.append(newNum); for i in range((size//2)-1, -1, -1): heapify(array, size, i) def deleteNode(array, num): size = len(array) i = 0 for i in range(0, size): if num == array(i): break array(i), array(size-1) = array(size-1), array(i) array.remove(num) for i in range((len(array)//2)-1, -1, -1): heapify(array, len(array), i) arr = () insert(arr, 3) insert(arr, 4) insert(arr, 9) insert(arr, 5) insert(arr, 2) print ("Max-Heap array: " + str(arr)) deleteNode(arr, 4) print("After deleting an element: " + str(arr))

  // Max-Heap data structure in Java 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(); ) 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); ) )

 // Max-Heap data structure in C #include int size = 0; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(int array(), int size, int i) ( if (size == 1) ( printf("Single element in the heap"); ) else ( int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l array(largest)) largest = l; if (r array(largest)) largest = r; if (largest != i) ( swap(&array(i), &array(largest)); heapify(array, size, largest); ) ) ) void insert(int array(), int newNum) ( if (size == 0) ( array(0) = newNum; size += 1; ) else ( array(size) = newNum; size += 1; for (int i = size / 2 - 1; i>= 0; i--) ( heapify(array, size, i); ) ) ) void deleteRoot(int array(), int num) ( int i; for (i = 0; i  = 0; i--) ( heapify(array, size, i); ) ) void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) printf("%d ", array(i)); printf(""); ) int main() ( int array(10); insert(array, 3); insert(array, 4); insert(array, 9); insert(array, 5); insert(array, 2); printf("Max-Heap array: "); printArray(array, size); deleteRoot(array, 4); printf("After deleting an element: "); printArray(array, size); )

 // Max-Heap data structure in C++ #include #include using namespace std; void swap(int *a, int *b) ( int temp = *b; *b = *a; *a = temp; ) void heapify(vector &hT, int i) ( int size = hT.size(); int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l hT(largest)) largest = l; if (r hT(largest)) largest = r; if (largest != i) ( swap(&hT(i), &hT(largest)); heapify(hT, largest); ) ) void insert(vector &hT, int newNum) ( int size = hT.size(); if (size == 0) ( hT.push_back(newNum); ) else ( hT.push_back(newNum); for (int i = size / 2 - 1; i>= 0; i--) ( heapify(hT, i); ) ) ) void deleteNode(vector &hT, int num) ( int size = hT.size(); int i; for (i = 0; i  = 0; i--) ( heapify(hT, i); ) ) void printArray(vector &hT) ( for (int i = 0; i < hT.size(); ++i) cout << hT(i) << " "; cout << ""; ) int main() ( vector heapTree; insert(heapTree, 3); insert(heapTree, 4); insert(heapTree, 9); insert(heapTree, 5); insert(heapTree, 2); cout << "Max-Heap array: "; printArray(heapTree); deleteNode(heapTree, 4); cout << "After deleting an element: "; printArray(heapTree); )