Kaudžu datu struktūra

Šajā apmācībā jūs uzzināsiet, kāda ir kaudzes datu struktūra. Jūs atradīsit arī piemērus kaudzes operācijām C, C ++, Java un Python.

Kaudzes datu struktūra ir pilnīgs binārs koks, kas apmierina kaudzes īpašību . To sauc arī par bināro kaudzi .

Pilnīgs binārs koks ir īpašs binārs koks, kurā

  • katrs līmenis, izņemot, iespējams, pēdējo, ir aizpildīts
  • visi mezgli ir pēc iespējas tālāk pa kreisi

Kaudzes īpašums ir tā mezgla īpašums, kurā

  • (for max heap) katra mezgla atslēga vienmēr ir lielāka par tā pakārtoto mezglu / s, un saknes mezgla atslēga ir lielākā starp visiem pārējiem mezgliem;
  • (par min kaudzi) katra mezgla atslēga vienmēr ir mazāka par pakārtoto mezglu / -iem, un saknes mezgla atslēga ir mazākā starp visiem pārējiem mezgliem.

Kaudzes operācijas

Dažas svarīgas operācijas, kas veiktas ar kaudzi, ir aprakstītas zemāk kopā ar to algoritmiem.

Heapify

Heapify ir kaudzes datu struktūras izveides process no binārā koka. To izmanto, lai izveidotu Min-Heap vai Max-Heap.

  1. Ļaujiet ievades masīvam būt
  2. No masīva izveidojiet pilnu bināro koku
  3. Sāciet no pirmā bezmezglu mezgla indeksa, kura indeksu dod n/2 - 1.
  4. Iestatīt pašreizējo elementu ikā largest.
  5. Kreisā bērna indeksu dod 2i + 1un labo - 2i + 2.
    Ja vērtība leftChildir lielāka par currentElement(ti, elements ithindeksā), iestatiet leftChildIndexkā lielāko.
    Ja rightChildir lielāks par elementu largest, iestatiet rightChildIndexkā largest.
  6. Apmainiet largestarcurrentElement
  7. Atkārtojiet 3. – 7. Darbību, līdz apakškoki arī ir uzkrāti.

Algoritms

 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)

Lai izveidotu Max-Heap:

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

Min-Heap abiem leftChildun rightChildvisiem mezgliem jābūt mazākiem par vecāku.

Ievietojiet elementu kaudzē

Algoritms ievietošanai 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. Ievietojiet jauno elementu koka galā.
  2. Uzkrājiet koku.

Min Heap gadījumā iepriekšminētais algoritms tiek modificēts tā, lai parentNodetas vienmēr būtu mazāks par newNode.

Dzēst elementu no kaudzes

Algoritms dzēšanai Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Atlasiet dzēšamo elementu.
  2. Apmainiet to ar pēdējo elementu.
  3. Noņemiet pēdējo elementu.
  4. Uzkrājiet koku.

Min Heapam iepriekš algoritms tiek modificēts tā, lai abi childNodesbūtu lielāki par currentNode.

Skatīties (atrast maks. / Min)

Peek darbība atgriež maksimālo elementu no Max Heap vai minimālo elementu no Min Heap, neizdzēšot mezglu.

Gan Max kaudzei, gan Min Heap

 atgriezt rootNode

Izraksts-Maks. / Min

Extract-Max atgriež mezglu ar maksimālo vērtību pēc tā noņemšanas no Max Heap, bet Extract-Min atgriež mezglu ar minimālo pēc tam, kad tas ir noņemts no Min Heap.

Python, Java, C / C ++ piemēri

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

Kaudžu datu struktūras lietojumprogrammas

  • Kaudze tiek izmantota, īstenojot prioritāro rindu.
  • Dijkstra algoritms
  • Kaudžu kārtojums

Interesanti raksti...