Heap Datastruktur

I den här handledningen lär du dig vad heapdatastrukturen är. Du hittar också arbetsexempel på heap-operationer i C, C ++, Java och Python.

Heap-datastruktur är ett komplett binärt träd som uppfyller heap-egenskapen . Det kallas också som en binär hög .

Ett komplett binärt träd är ett speciellt binärt träd där

  • varje nivå, utom möjligen den sista, fylls
  • alla noder är så långt till vänster som möjligt

Heap Property är egenskapen för en nod där

  • (för max heap) nyckeln för varje nod är alltid större än dess undernod / er och nyckeln för rotnoden är den största bland alla andra noder;
  • (för min hög) nyckeln för varje nod är alltid mindre än undernoden / -erna och nyckeln till rotnoden är den minsta bland alla andra noder.

Heap-operationer

Några av de viktiga operationerna som utförs på en hög beskrivs nedan tillsammans med deras algoritmer.

Heapify

Heapify är processen att skapa en heap-datastruktur från ett binärt träd. Den används för att skapa en Min-Heap eller en Max-Heap.

  1. Låt inmatningsmatrisen vara
  2. Skapa ett komplett binärt träd från matrisen
  3. Börja från det första indexet för icke-bladnod vars index ges av n/2 - 1.
  4. Ställ in aktuellt element isom largest.
  5. Indexet för vänster barn ges av 2i + 1och det högra barnet ges av 2i + 2.
    Om leftChildär större än currentElement(dvs element vid ithindex), ställ in leftChildIndexsom störst.
    Om rightChildär större än elementet i largest, ställ in rightChildIndexsom largest.
  6. Byt largestmedcurrentElement
  7. Upprepa steg 3-7 tills underträdet också heapifieras.

Algoritm

 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å här skapar du en Max-Heap:

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

För Min-Heap, både leftChildoch rightChildmåste vara mindre än den överordnade för alla noder.

Infoga Element i Heap

Algoritm för infogning 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. Sätt in det nya elementet i slutet av trädet.
  2. Heapify trädet.

För Min Heap modifieras ovanstående algoritm så att den parentNodealltid är mindre än newNode.

Ta bort Element från Heap

Algoritm för radering i Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Välj det element som ska raderas.
  2. Byt det med det sista elementet.
  3. Ta bort det sista elementet.
  4. Heapify trädet.

För Min Heap ändras ovanstående algoritm så att båda childNodesär större än currentNode.

Titta (hitta max / min)

Peek-operationen returnerar det maximala elementet från Max Heap eller minimi-elementet från Min Heap utan att noden raderas.

För både Max heap och Min Heap

 returnera rootNode

Extract-Max / Min

Extract-Max returnerar noden med maximalt värde efter att ha tagit bort den från en Max Heap medan Extract-Min returnerar noden med minimum efter att ha tagit bort den från Min Heap.

Python, Java, C / C ++ exempel

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 Data Structure Applications

  • Heap används när en prioritetskö implementeras.
  • Dijkstras algoritm
  • Heap Sort

Intressanta artiklar...