Heap-gegevensstructuur

In deze zelfstudie leert u wat heap-gegevensstructuur is. Ook vindt u werkende voorbeelden van heap-bewerkingen in C, C ++, Java en Python.

Heap-gegevensstructuur is een complete binaire boom die voldoet aan de heap-eigenschap . Het wordt ook wel een binaire heap genoemd .

Een complete binaire boom is een speciale binaire boom waarin

  • elk niveau, behalve mogelijk het laatste, is gevuld
  • alle knooppunten zijn zo ver mogelijk links

Heap-eigenschap is de eigenschap van een knooppunt waarin

  • (voor max heap) sleutel van elk knooppunt is altijd groter dan zijn kindknooppunt (en) en de sleutel van het hoofdknooppunt is de grootste van alle andere knooppunten;
  • (voor min heap) sleutel van elk knooppunt is altijd kleiner dan de onderliggende knooppunt (en) en de sleutel van het hoofdknooppunt is de kleinste van alle andere knooppunten.

Heap-operaties

Enkele van de belangrijke bewerkingen die op een heap worden uitgevoerd, worden hieronder samen met hun algoritmen beschreven.

Heapify

Heapify is het proces waarbij een heap-gegevensstructuur wordt gemaakt op basis van een binaire boom. Het wordt gebruikt om een ​​Min-Heap of een Max-Heap te maken.

  1. Laat de invoerarray zijn
  2. Maak een volledige binaire boom van de array
  3. Begin met de eerste index van niet-bladknooppunten waarvan de index wordt gegeven door n/2 - 1.
  4. Stel het huidige element in ials largest.
  5. De index van het linkerkind wordt gegeven door 2i + 1en het rechterkind wordt gegeven door 2i + 2.
    Als leftChildgroter is dan currentElement(dwz element bij ithindex), stel dan in leftChildIndexals grootste.
    Als rightChildgroter is dan element in largest, stelt u in rightChildIndexals largest.
  6. Wissel largestmetcurrentElement
  7. Herhaal stap 3-7 totdat de substructuren ook zijn opgehoopt.

Algoritme

 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)

Om een ​​Max-Heap te maken:

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

Voor Min-Heap moeten beide leftChilden rightChildkleiner zijn dan de bovenliggende waarde voor alle knooppunten.

Element invoegen in Heap

Algoritme voor invoeging 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. Voeg het nieuwe element aan het einde van de boom toe.
  2. Heapify de boom.

Voor Min Heap is het bovenstaande algoritme aangepast zodat het parentNodealtijd kleiner is dan newNode.

Element verwijderen uit heap

Algoritme voor verwijdering in Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Selecteer het element dat u wilt verwijderen.
  2. Verwissel het met het laatste element.
  3. Verwijder het laatste element.
  4. Heapify de boom.

Voor Min Heap is het bovenstaande algoritme aangepast zodat beide childNodesgroter zijn dan currentNode.

Peek (zoek max / min)

De Peek-bewerking retourneert het maximumelement uit Max Heap of minimumelement uit Min Heap zonder het knooppunt te verwijderen.

Voor zowel Max heap als Min Heap

 retourneer rootNode

Extract-Max / Min

Extract-Max retourneert het knooppunt met de maximale waarde nadat het uit een Max Heap is verwijderd, terwijl Extract-Min het knooppunt met een minimum retourneert nadat het uit de Min Heap is verwijderd.

Python, Java, C / C ++ voorbeelden

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-gegevensstructuurapplicaties

  • Heap wordt gebruikt tijdens het implementeren van een prioriteitswachtrij.
  • Dijkstra's algoritme
  • Heap Sorteren

Interessante artikelen...