Structura de date Heap

În acest tutorial, veți afla ce este structura de date heap. De asemenea, veți găsi exemple de lucru ale operațiilor de heap în C, C ++, Java și Python.

Structura de date Heap este un arbore binar complet care satisface proprietatea heap . Este, de asemenea, numit ca o grămadă binară .

Un copac binar complet este un copac binar special în care

  • fiecare nivel, cu excepția eventuală a ultimului, este completat
  • toate nodurile sunt cât mai departe posibil

Proprietatea Heap este proprietatea unui nod în care

  • (pentru heap maxim) cheia fiecărui nod este întotdeauna mai mare decât nodul / nodurile sale copil și cheia nodului rădăcină este cea mai mare dintre toate celelalte noduri;
  • (pentru min heap) cheia fiecărui nod este întotdeauna mai mică decât nodul / nodurile copil, iar cheia nodului rădăcină este cea mai mică dintre toate celelalte noduri.

Operații Heap

Unele dintre operațiunile importante efectuate pe o grămadă sunt descrise mai jos împreună cu algoritmii lor.

Heapify

Heapify este procesul de creare a unei structuri de date heap dintr-un arbore binar. Este folosit pentru a crea un Min-Heap sau un Max-Heap.

  1. Să fie matricea de intrare
  2. Creați un arbore binar complet din matrice
  3. Începeți de la primul index al nodului non-frunză al cărui index este dat de n/2 - 1.
  4. Setați elementul curent ica largest.
  5. Indicele copilului stâng este dat de 2i + 1și copilul drept este dat de 2i + 2.
    Dacă leftChildeste mai mare decât currentElement(adică element la ithindex), setați leftChildIndexca cel mai mare.
    În cazul în care rightChildeste mai mare decât element largest, stabilit rightChildIndexca largest.
  6. Schimbați largestcucurrentElement
  7. Repetați pașii 3-7 până când subarborii sunt, de asemenea, heapified.

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)

Pentru a crea un Max-Heap:

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

Pentru Min-Heap, ambele leftChildși rightChildtrebuie să fie mai mici decât părintele pentru toate nodurile.

Introduceți elementul în grămadă

Algoritm pentru inserare în 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. Introduceți noul element la capătul arborelui.
  2. Heapify copac.

Pentru Min Heap, algoritmul de mai sus este modificat astfel încât să parentNodefie întotdeauna mai mic decât newNode.

Ștergeți elementul din heap

Algoritm pentru ștergere în Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Selectați elementul de șters.
  2. Schimbați-l cu ultimul element.
  3. Eliminați ultimul element.
  4. Heapify copac.

Pentru Min Heap, algoritmul de mai sus este modificat astfel încât ambele să childNodesfie mai mici decât currentNode.

Peek (Găsiți max / min)

Operația Peek returnează elementul maxim din Max Heap sau elementul minim din Min Heap fără a șterge nodul.

Atât pentru Max heap, cât și pentru Min Heap

 returnează rootNode

Extract-Max / Min

Extract-Max returnează nodul cu valoare maximă după ce îl scoate dintr-un Heap Max, în timp ce Extract-Min returnează nodul cu minimum după ce îl scoate din Heap Min.

Exemple 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); )

Aplicații de structură de date Heap

  • Heap este utilizat în timpul implementării unei cozi prioritare.
  • Algoritmul lui Dijkstra
  • Sortare în grămadă

Articole interesante...