Hromadná datová struktura

V tomto kurzu se dozvíte, co je halda datová struktura. Také najdete pracovní příklady haldy operací v C, C ++, Java a Python.

Struktura dat haldy je kompletní binární strom, který splňuje vlastnost haldy . Nazývá se také jako binární halda .

Kompletní binární strom je speciální binární strom, ve kterém

  • každá úroveň, s výjimkou poslední, je zaplněna
  • všechny uzly jsou co nejvíce vlevo

Vlastnost haldy je vlastnost uzlu, ve kterém

  • (pro maximální haldu) klíč každého uzlu je vždy větší než jeho podřízený uzel a klíč kořenového uzlu je největší ze všech ostatních uzlů;
  • (pro min. haldu) klíč každého uzlu je vždy menší než podřízený uzel / s a ​​klíč kořenového uzlu je nejmenší ze všech ostatních uzlů.

Haldy operace

Některé důležité operace prováděné na haldě jsou popsány níže spolu s jejich algoritmy.

Heapify

Heapify je proces vytváření struktury haldy dat z binárního stromu. Používá se k vytvoření minimální hromady nebo maximální hromady.

  1. Nechť je vstupní pole
  2. Vytvořte z pole kompletní binární strom
  3. Začněte od prvního indexu nelistového uzlu, jehož index je dán n/2 - 1.
  4. Nastavit aktuální prvek ijako largest.
  5. Index levého dítěte je dán 2i + 1a pravé dítě je dáno 2i + 2.
    Pokud leftChildje větší než currentElement(tj. Prvek v ithindexu), nastavte leftChildIndexjako největší.
    Pokud rightChildje větší než element v largest, nastavte rightChildIndexjako largest.
  6. Zaměnit largestzacurrentElement
  7. Opakujte kroky 3–7, dokud nebudou také podstromy heapifikovány.

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)

Vytvoření hromady Max:

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

U Min-Heap obojí leftChilda rightChildmusí být menší než nadřazený pro všechny uzly.

Vložte prvek do haldy

Algoritmus pro vložení 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ý prvek na konec stromu.
  2. Heapify strom.

U Min Heap je výše uvedený algoritmus upraven tak, aby parentNodebyl vždy menší než newNode.

Odstranit prvek z haldy

Algoritmus pro smazání v Max haldě

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Vyberte prvek, který chcete odstranit.
  2. Zaměňte jej za poslední prvek.
  3. Odeberte poslední prvek.
  4. Heapify strom.

U Min Heap je výše uvedený algoritmus upraven tak, aby oba childNodesbyly větší než currentNode.

Peek (Najít max / min)

Peek operace vrátí maximální prvek z Max Heap nebo minimální prvek z Min Heap bez odstranění uzlu.

Pro haldy Max i Min Haldy

 vrátit rootNode

Extrakt-Max / Min

Extract-Max vrátí uzel s maximální hodnotou po odebrání z Max Heap, zatímco Extract-Min vrátí uzel s minimem po odebrání z Min Heap.

Python, Java, C / C ++ příklady

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

Aplikace haldy datové struktury

  • Halda se používá při implementaci prioritní fronty.
  • Dijkstrův algoritmus
  • Třídění haldy

Zajímavé články...