Hromadná dátová štruktúra

V tomto výučbe sa dozviete, čo je halda dátová štruktúra. Nájdete tiež pracovné príklady haldy operácií v jazykoch C, C ++, Java a Python.

Haldová dátová štruktúra je kompletný binárny strom, ktorý vyhovuje vlastnosti haldy . Nazýva sa tiež ako binárna halda .

Kompletný binárny strom je špeciálny binárny strom, v ktorom

  • je vyplnená každá úroveň, okrem poslednej
  • všetky uzly sú čo najviac vľavo

Heap Property je vlastnosť uzla, v ktorom

  • (pre maximálnu haldu) kľúč každého uzla je vždy väčší ako jeho podradený uzol a kľúč koreňového uzla je najväčší zo všetkých ostatných uzlov;
  • (pre minimálnu haldu) kľúč každého uzla je vždy menší ako podradený uzol a kľúč koreňového uzla je najmenší zo všetkých ostatných uzlov.

Haldy operácie

Niektoré dôležité operácie vykonávané na halde sú opísané nižšie spolu s ich algoritmami.

Heapify

Heapify je proces vytvárania haldy dátovej štruktúry z binárneho stromu. Používa sa na vytvorenie minimálnej alebo maximálnej haldy.

  1. Nech je vstupné pole
  2. Vytvorte z poľa kompletný binárny strom
  3. Začnite od prvého indexu nelistového uzla, ktorého index je daný n/2 - 1.
  4. Nastaviť aktuálny prvok iako largest.
  5. Index ľavého dieťaťa je daný 2i + 1a pravé dieťa je dané 2i + 2.
    Ak leftChildje väčšie ako currentElement(tj. Prvok v ithindexe), nastavte leftChildIndexako najväčšie.
    Ak rightChildje väčšie ako prvok v largest, nastavte rightChildIndexako largest.
  6. Zamieňajte largestscurrentElement
  7. Opakujte kroky 3 až 7, kým nebudú tiež podstromy heapifikované.

Algoritmus

 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)

Vytvorenie maximálnej haldy:

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

Pre Min-Heap musia byť obidve leftChilda rightChildmusia byť menšie ako rodič pre všetky uzly.

Vložte prvok do haldy

Algoritmus pre vloženie do Max. Haldy

 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. Vložte nový prvok na koniec stromu.
  2. Heapify strom.

Pre Min Heap je vyššie uvedený algoritmus upravený tak, aby parentNodebol vždy menší ako newNode.

Odstrániť prvok z haldy

Algoritmus na vymazanie v Max. Halde

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Vyberte prvok, ktorý sa má vymazať.
  2. Zamieňajte ho s posledným prvkom.
  3. Odstráňte posledný prvok.
  4. Heapify strom.

Pre Min Heap je vyššie uvedený algoritmus upravený tak, aby oba childNodesboli väčšie ako currentNode.

Nahliadnuť (nájsť max / min)

Peek operácia vráti maximálny prvok z Max Heap alebo minimálny element z Min Heap bez odstránenia uzla.

Pre haldy Max aj Min Haldy

 návrat rootNode

Extrakt - max / min

Extract-Max vráti uzol s maximálnou hodnotou po odstránení z Max Heap, zatiaľ čo Extract-Max vráti uzol s minimom po odstránení z Min Heap.

Príklady jazyka 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); )

Haldy dátových štruktúr aplikácií

  • Halda sa používa pri implementácii prioritného frontu.
  • Dijkstraov algoritmus
  • Hromadné triedenie

Zaujímavé články...