Hunniku andmete struktuur

Selles õpetuses saate teada, mis on kuhjaga andmete struktuur. Samuti leiate toimivaid näiteid kuhjaoperatsioonide kohta C, C ++, Java ja Pythonis.

Kuhja andmestruktuur on täielik binaarne puu, mis rahuldab kuhja omadust . Seda nimetatakse ka binaarhunnikuks .

Täielik binaarne puu on spetsiaalne binaarne puu, milles

  • iga tase, välja arvatud viimane, on täidetud
  • kõik sõlmed jäävad võimalikult vasakule

Kuhu omadus on sõlme omadus, milles

  • (maksimaalse kuhja jaoks) on iga sõlme võti alati suurem kui tema alamsõlm (id) ja juursõlme võti on kõigi teiste sõlmede seas suurim;
  • (min kuhja jaoks) on iga sõlme võti alati väiksem kui alamsõlm (id) ja juursõlme võti on kõigi teiste sõlmede seas väikseim.

Kuhjaoperatsioonid

Mõned olulised kuhjaga tehtavad toimingud on kirjeldatud koos nende algoritmidega.

Heapify

Heapify on kuhjaga andmestruktuuri loomine kahendpuust. Seda kasutatakse Min-Heap või Max-Heap loomiseks.

  1. Laske sisendimassiiv olla
  2. Looge massiivist täielik binaarne puu
  3. Alustage mitte-lehesõlme esimesest indeksist, mille indeksi annab n/2 - 1.
  4. Määra praegune element inagu largest.
  5. Vasakpoolse lapse indeksi annab 2i + 1ja õige lapse 2i + 2.
    If leftChildon suurem kui currentElement(st ithindeksis olev element ), määrake leftChildIndexsuurimaks.
    Kui rightChildon suurem kui element largest, seada rightChildIndexnii largest.
  6. Vaheta largestkooscurrentElement
  7. Korrake samme 3-7, kuni ka alampuud on kuhjunud.

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)

Max-Heap'i loomiseks toimige järgmiselt.

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

Min-Heap'i puhul peavad mõlemad leftChildja rightChildolema kõigi sõlmede jaoks vanemast väiksemad.

Sisestage element kuhja

Max Heapisse sisestamise algoritm

 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. Sisestage uus element puu otsa.
  2. Hange puu.

Min Heap'i puhul muudetakse ülaltoodud algoritmi nii, et see parentNodeoleks alati väiksem kui newNode.

Kustuta element kuhjast

Kustutamise algoritm Max Heapis

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Valige kustutatav element.
  2. Vahetage see viimase elemendiga.
  3. Eemaldage viimane element.
  4. Hange puu.

Min Heap'i puhul muudetakse ülaltoodud algoritmi nii, et mõlemad childNodesoleksid suuremad kui currentNode.

Peek (Leia max / min)

Peek-operatsioon tagastab maksimaalse elemendi maksimaalsest hunnikust või minimaalse elemendi mineraalsest hulgast sõlme kustutamata.

Nii Max kuhja kui ka Min Heap jaoks

 tagastage rootNode

Väljavõte-Max / Min

Extract-Max tagastab maksimaalse väärtusega sõlme pärast selle eemaldamist Max Heap'ist, samas kui Extract-Min tagastab sõlme minimaalsega pärast selle eemaldamist Min Heap'ist.

Pythoni, Java, C / C ++ näited

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

Hunniku andmestruktuuri rakendused

  • Prioriteetse järjekorra rakendamisel kasutatakse kuhja.
  • Dijkstra algoritm
  • Hunnik Sorteeri

Huvitavad Artiklid...