Heap-datastruktur

I denne vejledning lærer du, hvad bunke datastruktur er. Du finder også arbejdseksempler på bunkeoperationer i C, C ++, Java og Python.

Heap-datastruktur er et komplet binært træ, der tilfredsstiller heap-ejendommen . Det kaldes også som en binær bunke .

Et komplet binært træ er et specielt binært træ, hvori

  • hvert niveau, undtagen muligvis det sidste, er udfyldt
  • alle knudepunkter er så langt tilbage som muligt

Heap Property er ejendommen til en node, hvor

  • (for max heap) nøglen til hver node er altid større end dens underliggende node / r, og nøglen til rodnoden er den største blandt alle andre noder;
  • (for min heap) nøglen til hver node er altid mindre end den underliggende node / r, og nøglen til rodnoden er den mindste blandt alle andre noder.

Bunkeoperationer

Nogle af de vigtige operationer, der udføres på en bunke, er beskrevet nedenfor sammen med deres algoritmer.

Heapify

Heapify er processen med at oprette en bunke-datastruktur fra et binært træ. Det bruges til at oprette en Min-Heap eller en Max-Heap.

  1. Lad input array være
  2. Opret et komplet binært træ fra arrayet
  3. Start fra det første indeks for ikke-bladknude, hvis indeks er givet af n/2 - 1.
  4. Indstil det aktuelle element isom largest.
  5. Indekset for venstre barn er givet af 2i + 1og det højre barn er givet af 2i + 2.
    Hvis leftChilder større end currentElement(dvs. element ved ithindeks), indstilles leftChildIndexsom størst.
    Hvis rightChilder større end element i largest, skal du indstille rightChildIndexsom largest.
  6. Byt largestmedcurrentElement
  7. Gentag trin 3-7, indtil undertrærne også heapificeres.

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)

Sådan oprettes en Max-Heap:

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

Til Min-Heap, både leftChildog rightChildskal være mindre end den forælder for alle knuder.

Indsæt element i bunke

Algoritme til indsættelse i 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. Indsæt det nye element i slutningen af ​​træet.
  2. Hæv træet.

For Min Heap ændres ovenstående algoritme, så den parentNodealtid er mindre end newNode.

Slet element fra bunke

Algoritme til sletning i Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Vælg det element, der skal slettes.
  2. Skift det med det sidste element.
  3. Fjern det sidste element.
  4. Hæv træet.

For Min Heap ændres ovenstående algoritme, så begge childNodeser større mindre end currentNode.

Kig (Find maks / min)

Peek-operation returnerer det maksimale element fra Max Heap eller minimum element fra Min Heap uden at slette noden.

For både Max bunke og Min bunke

 returner rootNode

Uddrag-maks / min

Extract-Max returnerer noden med maksimal værdi efter at have fjernet den fra en Max Heap, mens Extract-Min returnerer noden med minimum efter at have fjernet den fra Min Heap.

Python, Java, C / C ++ eksempler

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 Datastruktur applikationer

  • Heap bruges under implementering af en prioritetskø.
  • Dijkstras algoritme
  • Heap Sort

Interessante artikler...