Kasan tietorakenne

Tässä opetusohjelmassa opit, mikä on kasan tietorakenne. Löydät myös toimivia esimerkkejä kasanoperaatioista C, C ++, Java ja Python.

Heap-tietorakenne on täydellinen binääripuu, joka täyttää kasan ominaisuuden . Sitä kutsutaan myös binääriseksi kasaksi .

Täydellinen binääripuu on erityinen binääripuu, jossa

  • jokainen taso, mahdollisesti viimeistä lukuun ottamatta, on täytetty
  • kaikki solmut ovat mahdollisimman vasemmalla

Heap Property on solmun ominaisuus, jossa

  • jokaisen solmun (maks. kasaan) avain on aina suurempi kuin sen alisolmu / s ja juurisolmun avain on kaikkien muiden solmujen suurin;
  • Kunkin solmun (min. kasaan) avain on aina pienempi kuin lapsisolmu / s ja juurisolmun avain on pienin kaikista muista solmuista.

Kasaoperaatiot

Jotkut kasalle suoritetuista tärkeistä operaatioista on kuvattu alla yhdessä niiden algoritmien kanssa.

Heapify

Heapify on kasan tietorakenteen luominen binääripuusta. Sitä käytetään luomaan Min-Heap tai Max-Heap.

  1. Olkoon syöttötaulukko
  2. Luo taulukosta täydellinen binääripuu
  3. Aloita ei-lehtisolmun ensimmäisestä indeksistä, jonka indeksin antaa n/2 - 1.
  4. Aseta nykyinen elementti iarvoksi largest.
  5. Vasemman lapsen indeksin antaa 2i + 1ja oikean lapsen antaa 2i + 2.
    Jos leftChildon suurempi kuin currentElement(eli elementti ithindeksissä), aseta leftChildIndexsuurin.
    Jos rightChildon suurempi kuin osa largest, asetetaan rightChildIndexniin largest.
  6. Vaihda largestkanssacurrentElement
  7. Toista vaiheet 3-7, kunnes myös alipuut kasautuvat.

Algoritmi

 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)

Suuren kasan luominen:

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

Min-Heapin molempien leftChildja niiden rightChildon oltava pienempiä kuin kaikkien solmujen vanhempi.

Aseta elementti kasaan

Algoritmi lisäykseen Max Heapiin

 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. Lisää uusi elementti puun päähän.
  2. Kasvata puuta.

Min Heapia varten yllä olevaa algoritmia muokataan siten, että se parentNodeon aina pienempi kuin newNode.

Poista elementti kasasta

Poistamisalgoritmi Max Heapissa

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Valitse poistettava elementti.
  2. Vaihda se viimeisen elementin kanssa.
  3. Poista viimeinen elementti.
  4. Kasvata puuta.

Min Heapille yllä olevaa algoritmia muokataan niin, että molemmat childNodesovat pienempiä kuin currentNode.

Kurkistaa (Etsi max / min)

Peek-toiminto palauttaa enimmäiselementin Max Heapista tai minimielementin Min Heapista poistamatta solmua.

Sekä Max-kasalle että Min-kasalle

 palauta rootNode

Pura-Max / Min

Extract-Max palauttaa solmun suurimmalla arvolla sen jälkeen, kun se on poistettu Max-kasasta, kun taas Extract-Min palauttaa solmun minimillä sen poistamisen jälkeen Min-kasasta.

Python, Java, C / C ++ Esimerkkejä

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

Kasan tietorakennesovellukset

  • Kasaa käytetään prioriteettijonoa toteutettaessa.
  • Dijkstran algoritmi
  • Kasa Lajittele

Mielenkiintoisia artikkeleita...