Struktur Data Heap

Dalam tutorial ini, Anda akan mempelajari apa itu struktur data heap. Selain itu, Anda akan menemukan contoh kerja operasi heap di C, C ++, Java dan Python.

Struktur data heap adalah pohon biner lengkap yang memenuhi properti heap . Ini juga disebut sebagai heap biner .

Pohon biner lengkap adalah pohon biner khusus yang di dalamnya

  • setiap level, kecuali mungkin yang terakhir, terisi
  • semua node berada sejauh mungkin

Properti Heap adalah properti node di mana

  • (untuk max heap) kunci setiap node selalu lebih besar dari node turunannya dan kunci dari node root adalah yang terbesar di antara semua node lainnya;
  • (untuk min heap) kunci setiap node selalu lebih kecil dari node anak / s dan kunci dari node root adalah yang terkecil di antara semua node lainnya.

Operasi Heap

Beberapa operasi penting yang dilakukan pada heap dijelaskan di bawah ini bersama dengan algoritmanya.

Heapify

Heapify adalah proses pembuatan struktur data heap dari pohon biner. Ini digunakan untuk membuat Min-Heap atau Max-Heap.

  1. Biarkan array input menjadi
  2. Buat pohon biner lengkap dari larik
  3. Mulai dari indeks pertama dari simpul non-daun yang indeksnya diberikan oleh n/2 - 1.
  4. Tetapkan elemen saat ini isebagai largest.
  5. Indeks anak kiri diberikan oleh 2i + 1dan anak kanan diberikan oleh 2i + 2.
    Jika leftChildlebih besar dari currentElement(yaitu elemen pada ithindeks), tetapkan leftChildIndexsebagai terbesar.
    Jika rightChildlebih besar dari elemen dalam largest, setel rightChildIndexsebagai largest.
  6. Tukar largestdengancurrentElement
  7. Ulangi langkah 3-7 sampai subpohon juga ditumpuk.

Algoritma

 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)

Untuk membuat Max-Heap:

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

Untuk Min-Heap, keduanya leftChilddan rightChildharus lebih kecil dari induk untuk semua node.

Sisipkan Elemen ke Heap

Algoritma untuk penyisipan di 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. Sisipkan elemen baru di ujung pohon.
  2. Heapify the tree.

Untuk Min Heap, algoritma di atas dimodifikasi sehingga parentNodeselalu lebih kecil dari newNode.

Hapus Elemen dari Heap

Algoritma untuk penghapusan di Max Heap

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Pilih elemen yang akan dihapus.
  2. Tukar dengan elemen terakhir.
  3. Hapus elemen terakhir.
  4. Heapify the tree.

Untuk Min Heap, algoritma di atas dimodifikasi sehingga keduanya childNodeslebih kecil dari currentNode.

Peek (Temukan maks / mnt)

Operasi Peek mengembalikan elemen maksimum dari Max Heap atau elemen minimum dari Min Heap tanpa menghapus node.

Untuk tumpukan Max dan Min Heap

 kembalikan rootNode

Ekstrak-Max / Min

Extract-Max mengembalikan node dengan nilai maksimum setelah menghapusnya dari Max Heap sedangkan Extract-Min mengembalikan node dengan nilai minimum setelah menghapusnya dari Min Heap.

Contoh Python, Java, C / C ++

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

Aplikasi Struktur Data Heap

  • Heap digunakan saat mengimplementasikan antrian prioritas.
  • Algoritma Dijkstra
  • Urutan Heap

Artikel yang menarik...