Krūvos duomenų struktūra

Šioje pamokoje sužinosite, kas yra kaupo duomenų struktūra. Taip pat rasite veikiančių kaupimo operacijų pavyzdžių C, C ++, Java ir Python.

Kaupo duomenų struktūra yra visas dvejetainis medis, kuris tenkina kaupo savybę . Jis taip pat vadinamas dvejetainiu kaupu .

Visasis dvejetainis medis yra specialus dvejetainis medis, kuriame

  • kiekvienas lygis, išskyrus galbūt paskutinį, yra užpildytas
  • visi mazgai yra kuo toliau kairiau

„Heap Property“ yra mazgo, kuriame

  • (maksimaliam kaupui) kiekvieno mazgo raktas visada yra didesnis už antrinį mazgą (-us), o šakninio mazgo raktas yra didžiausias tarp visų kitų mazgų;
  • kiekvieno mazgo raktas visada yra mažesnis nei antrasis mazgas, o šakninio mazgo raktas yra mažiausias tarp visų kitų mazgų.

Krūvos operacijos

Kai kurios svarbios operacijos, atliekamos su kaupu, aprašomos žemiau kartu su jų algoritmais.

Heapify

„Heapify“ yra krūvos duomenų struktūros sukūrimo iš dvejetainio medžio procesas. Jis naudojamas sukurti „Min-Heap“ arba „Max-Heap“.

  1. Tegul įvesties masyvas bus
  2. Iš masyvo sukurkite visą dvejetainį medį
  3. Pradėkite nuo pirmojo ne lapų mazgo, kurio indeksą nurodo indeksas n/2 - 1.
  4. Nustatyti dabartinį elementą ikaip largest.
  5. Kairio vaiko indeksą nurodo, 2i + 1o dešinįjį - 2i + 2.
    Jei leftChildyra didesnis nei currentElement(ty elementas prie ithindekso), nustatykite leftChildIndexkaip didžiausią.
    Jei rightChildyra didesnis nei elementas largest, nustatykite rightChildIndexkaip largest.
  6. Keisti largestsucurrentElement
  7. Pakartokite 3-7 veiksmus, kol pogrupiai taip pat bus sukaupti.

Algoritmas

 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)

Norėdami sukurti maksimalų kaupą:

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

Dėl min-Heap, tiek leftChildir rightChildturi būti mažesnis nei visų mazgų tėvų.

Įdėkite elementą į kaupą

Įterpimo į „Max Heap“ algoritmas

 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. Įterpkite naują elementą medžio gale.
  2. Sukaupk medį.

Min Heap atveju minėtas algoritmas yra modifikuotas taip, kad parentNodevisada būtų mažesnis nei newNode.

Ištrinti elementą iš kaupo

Maks Heapo ištrynimo algoritmas

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Pasirinkite elementą, kurį norite ištrinti.
  2. Pakeiskite jį su paskutiniu elementu.
  3. Pašalinkite paskutinį elementą.
  4. Sukaupk medį.

Min Heap atveju aukščiau esantis algoritmas yra modifikuotas taip, kad abu childNodesbūtų didesni nei currentNode.

Žvilgtelėti (rasti maks. / Min.)

„Peek“ operacija grąžina maksimalų elementą iš „Max Heap“ arba minimalų elementą iš „Min Heap“, neištrindama mazgo.

Tiek Maxui, tiek Minui Heapui

 grąžinti rootNode

Ištrauka - maks. / Min

„Extract-Max“ grąžina mazgą su maksimalia verte, pašalinęs jį iš „Max Heap“, o „Extract-Min“ grąžina mazgą su minimaliu, pašalinus jį iš „Min Heap“.

„Python“, „Java“, „C / C ++“ pavyzdžiai

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

Krūvos duomenų struktūros programos

  • Kaupas naudojamas įgyvendinant prioritetinę eilę.
  • Dijkstros algoritmas
  • Krūvos rūšiavimas

Įdomios straipsniai...