Struktura podataka hrpe

U ovom uputstvu naučit ćete što je struktura podataka hrpe. Također ćete naći radne primjere operacija hrpe na C, C ++, Java i Python.

Struktura podataka hrpe cjelovito je binarno stablo koje zadovoljava svojstvo hrpe . Također se naziva i binarnom hrpom .

Kompletno binarno stablo je posebno binarno stablo u kojem

  • popunjena je svaka razina, osim moguće posljednje
  • svi čvorovi su što dalje lijevo

Svojstvo hrpe svojstvo je čvora u kojem

  • (za maksimalnu hrpu) ključ svakog čvora uvijek je veći od podređenih čvorova, a ključ korijenskog čvora najveći je među svim ostalim čvorovima;
  • (za min hrpu) ključ svakog čvora uvijek je manji od podređenih čvorova, a ključ korijenskog čvora najmanji je među svim ostalim čvorovima.

Operacije hrpe

Neke važne operacije izvedene na hrpi opisane su u nastavku zajedno s njihovim algoritmima.

Heapify

Heapify je postupak stvaranja strukture podataka hrpe od binarnog stabla. Koristi se za stvaranje Min-Heap ili Max-Heap.

  1. Neka ulazni niz bude
  2. Iz polja stvorite cjelovito binarno stablo
  3. Počnite od prvog indeksa nelistnog čvora čiji indeks daje n/2 - 1.
  4. Postavite trenutni element ikao largest.
  5. Indeks lijevog djeteta dat je s, 2i + 1a desnog djeteta 2i + 2.
    Ako leftChildje veće od currentElement(tj. Element u ithindeksu), postavi leftChildIndexkao najveći.
    Ako rightChildje veći od elementa u largest, postavite rightChildIndexkao largest.
  6. Zamijeni largestsacurrentElement
  7. Ponavljajte korake 3-7 dok se podstabla također ne pojačaju.

Algoritam

 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)

Da biste stvorili Max-Heap:

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

Za Min-Heap, oba leftChildi rightChildmoraju biti manja od nadređene za sve čvorove.

Umetnite element u hrpu

Algoritam za umetanje u 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. Umetnite novi element na kraj stabla.
  2. Ojačajte stablo.

Za Min Heap, gornji algoritam je izmijenjen tako da parentNodeje uvijek manji od newNode.

Izbriši element iz hrpe

Algoritam za brisanje u Max Heap-u

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Odaberite element koji želite izbrisati.
  2. Zamijenite ga posljednjim elementom.
  3. Uklonite posljednji element.
  4. Ojačajte stablo.

Za Min Heap, gornji algoritam je izmijenjen tako da su oba childNodesveća od currentNode.

Zaviri (pronađi maks. / Min)

Peek operacija vraća maksimalni element iz Max Heap ili minimalni element iz Min Heap bez brisanja čvora.

I za Max heap i Min Heap

 vrati rootNode

Izdvajanje-maks. / Min

Extract-Max vraća čvor s maksimalnom vrijednošću nakon uklanjanja iz Max Heap, dok Extract-Min vraća čvor s minimumom nakon uklanjanja iz Min Heap.

Primjeri Python, Java, C / C ++

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

Primjene strukture gomile podataka

  • Hrpa se koristi tijekom implementacije reda prioriteta.
  • Dijkstrin algoritam
  • Sortiranje po hrpi

Zanimljivi članci...