Heap-Datenstruktur

In diesem Tutorial erfahren Sie, wie die Heap-Datenstruktur aussieht. Außerdem finden Sie Arbeitsbeispiele für Heap-Operationen in C, C ++, Java und Python.

Die Heap-Datenstruktur ist ein vollständiger Binärbaum, der die Heap-Eigenschaft erfüllt . Es wird auch als binärer Heap bezeichnet .

Ein vollständiger Binärbaum ist ein spezieller Binärbaum, in dem

  • Jedes Level, außer möglicherweise das letzte, ist gefüllt
  • Alle Knoten sind so weit wie möglich links

Heap-Eigenschaft ist die Eigenschaft eines Knotens, in dem

  • (für max. Heap) Schlüssel jedes Knotens ist immer größer als seine untergeordneten Knoten und der Schlüssel des Wurzelknotens ist der größte unter allen anderen Knoten;
  • Der Schlüssel (für den minimalen Heap) jedes Knotens ist immer kleiner als der / die untergeordnete (n) Knoten und der Schlüssel des Wurzelknotens ist der kleinste unter allen anderen Knoten.

Heap-Operationen

Einige der wichtigen Operationen, die auf einem Heap ausgeführt werden, werden im Folgenden zusammen mit ihren Algorithmen beschrieben.

Heapify

Bei Heapify wird aus einem Binärbaum eine Heap-Datenstruktur erstellt. Es wird verwendet, um einen Min-Heap oder einen Max-Heap zu erstellen.

  1. Das Eingabearray sei
  2. Erstellen Sie einen vollständigen Binärbaum aus dem Array
  3. Beginnen Sie mit dem ersten Index des Nicht-Blattknotens, dessen Index durch gegeben ist n/2 - 1.
  4. Aktuelles Element einstellen ials largest.
  5. Der Index des linken Kindes ist gegeben durch 2i + 1und das rechte Kind ist gegeben durch 2i + 2.
    Wenn leftChildgrößer als currentElement(dh Element am ithIndex), wird leftChildIndexals größtes festgelegt.
    Wenn rightChildgrößer als Element in ist largest, setzen Sie rightChildIndexals largest.
  6. Tauschen Sie largestmitcurrentElement
  7. Wiederholen Sie die Schritte 3 bis 7, bis auch die Teilbäume häufen.

Algorithmus

 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)

So erstellen Sie einen Max-Heap:

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

Für Min-Heap müssen beide leftChildund rightChildfür alle Knoten kleiner als das übergeordnete Element sein.

Element in Heap einfügen

Algorithmus zum Einfügen in 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
  1. Fügen Sie das neue Element am Ende des Baums ein.
  2. Haufen Sie den Baum.

Für Min Heap wird der obige Algorithmus so geändert, dass er parentNodeimmer kleiner als ist newNode.

Element vom Heap löschen

Algorithmus zum Löschen in Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Wählen Sie das zu löschende Element aus.
  2. Tauschen Sie es mit dem letzten Element aus.
  3. Entfernen Sie das letzte Element.
  4. Haufen Sie den Baum.

Für Min Heap wird der obige Algorithmus so geändert, dass beide childNodesgrößer kleiner als sind currentNode.

Peek (Find max / min)

Die Peek-Operation gibt das maximale Element von Max Heap oder das minimale Element von Min Heap zurück, ohne den Knoten zu löschen.

Für Max Heap und Min Heap

 return rootNode

Extrakt-Max / Min

Extract-Max gibt den Knoten mit dem Maximalwert zurück, nachdem er aus einem Max-Heap entfernt wurde, während Extract-Min den Knoten mit dem Minimum zurückgibt, nachdem er aus dem Min-Heap entfernt wurde.

Beispiele für 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); )

Heap-Datenstrukturanwendungen

  • Heap wird beim Implementieren einer Prioritätswarteschlange verwendet.
  • Dijkstra-Algorithmus
  • Heap Sort

Interessante Beiträge...