Struktura podatkov kopice

V tej vadnici boste izvedeli, kaj je struktura podatkov o kopici. Prav tako boste našli delovne primere kopičenja v C, C ++, Java in Python.

Struktura podatkov kopice je popolno binarno drevo, ki izpolnjuje lastnost kopice . Imenuje se tudi kot binarna kopica .

Popolno binarno drevo je posebno binarno drevo, v katerem

  • zapolni se vsaka stopnja, razen morda zadnje
  • vsa vozlišča so čim bolj levo

Lastnost kopice je lastnost vozlišča, v katerem

  • (za največ kopij) je ključ vsakega vozlišča vedno večji od njegovega podrejenega vozlišča, ključ korenskega vozlišča pa je največji med vsemi drugimi vozlišči;
  • (za min heap) ključ vsakega vozlišča je vedno manjši od podrejenega vozlišča / vozlišč in ključ korenskega vozlišča je najmanjši med vsemi drugimi vozlišči.

Operacije kopice

Nekatere pomembne operacije, ki se izvajajo na kopici, so opisane spodaj skupaj z njihovimi algoritmi.

Heapify

Heapify je postopek ustvarjanja podatkovne strukture kopice iz binarnega drevesa. Uporablja se za ustvarjanje Min-Heap ali Max-Heap.

  1. Vhodno polje naj bo
  2. Iz matrike ustvarite popolno binarno drevo
  3. Začnite s prvim indeksom nelistnega vozlišča, katerega indeks je podan z n/2 - 1.
  4. Nastavi trenutni element ikot largest.
  5. Indeks levega otroka je podan z, 2i + 1desni otrok pa z 2i + 2.
    Če leftChildje večje od currentElement(tj. Element v ithindeksu), nastavite leftChildIndexkot največjega.
    Če rightChildje večji od elementa v largest, nastavite rightChildIndexkot largest.
  6. Zamenjaj largestzcurrentElement
  7. Ponavljajte korake 3-7, dokler se poddrevesa tudi ne zgostijo.

Algoritem

 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)

Če želite ustvariti Max-Heap:

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

Za Min-Heap morata biti oba leftChildin rightChildmorata biti manjša od nadrejene za vsa vozlišča.

Vstavite element v kup

Algoritem za vstavljanje v 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. Na koncu drevesa vstavite nov element.
  2. Onesnaži drevo.

Za Min Heap je zgornji algoritem spremenjen tako, da parentNodeje vedno manjši od newNode.

Izbriši element iz kopice

Algoritem za brisanje v Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Izberite element, ki ga želite izbrisati.
  2. Zamenjajte ga z zadnjim elementom.
  3. Odstranite zadnji element.
  4. Onesnaži drevo.

Za Min Heap je zgornji algoritem spremenjen tako, da sta oba childNodesvečja od currentNode.

Peek (Najdi največ / min)

Operacija Peek vrne največ element iz Max Heap ali najmanjši element iz Min Heap brez brisanja vozlišča.

Tako za Max heap kot za Min Heap

 vrni rootNode

Extract-Max / Min

Extract-Max vrne vozlišče z največjo vrednostjo, potem ko ga odstrani iz Max Heap, medtem ko Extract-Min vrne vozlišče z minimumom, potem ko ga odstrani iz Min Heap.

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

Aplikacije podatkovne strukture kopice

  • Kopiček se uporablja med izvajanjem prednostne čakalne vrste.
  • Dijkstrin algoritem
  • Razvrsti kup

Zanimive Članki...