Struktur Data timbunan

Dalam tutorial ini, anda akan mengetahui apa itu struktur data timbunan. Anda juga akan mendapat contoh operasi timbunan di C, C ++, Java dan Python.

Struktur data timbunan adalah pokok binari lengkap yang memenuhi harta timbunan . Ia juga dipanggil sebagai timbunan binari .

Pokok binari lengkap adalah pokok binari khas di mana

  • setiap peringkat, kecuali mungkin yang terakhir, dipenuhi
  • semua nod berada sejauh kiri mungkin

Heap Property adalah harta suatu simpul di mana

  • kekunci (untuk timbunan maksimum) setiap nod selalu lebih besar daripada simpul anak dan kunci simpul akar adalah yang terbesar di antara semua nod lain;
  • (untuk timbunan min) kunci setiap nod sentiasa lebih kecil daripada simpul anak dan kunci nod akar adalah yang terkecil di antara semua nod lain.

Operasi Tumpukan

Beberapa operasi penting yang dilakukan pada timbunan dijelaskan di bawah bersama dengan algoritma mereka.

Tumpukan

Heapify adalah proses membuat struktur data timbunan dari pokok binari. Ia digunakan untuk membuat Min-Heap atau Max-Heap.

  1. Biarkan array input menjadi
  2. Buat pokok binari lengkap dari tatasusunan
  3. Mulakan dari indeks pertama simpul bukan daun yang indeksnya diberikan oleh n/2 - 1.
  4. Tetapkan elemen semasa isebagai largest.
  5. Indeks anak kiri diberikan oleh 2i + 1dan anak kanan diberikan oleh 2i + 2.
    Sekiranya leftChildlebih besar daripada currentElement(iaitu elemen pada ithindeks), tetapkan leftChildIndexsebagai yang terbesar.
    Sekiranya rightChildlebih besar daripada elemen dalam largest, tetapkan rightChildIndexsebagai largest.
  6. Tukar largestdengancurrentElement
  7. Ulangi langkah 3-7 sehingga subtumbuhan juga bertambah.

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 rightChildmestilah lebih kecil daripada induk untuk semua nod.

Masukkan Elemen ke dalam timbunan

Algoritma untuk penyisipan dalam 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. Masukkan elemen baru di hujung pokok.
  2. Memanaskan pokok.

Untuk Min Heap, algoritma di atas diubah suai agar parentNodeselalu lebih kecil daripada newNode.

Padamkan Elemen dari Tumpukan

Algoritma untuk penghapusan dalam 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 dihapuskan.
  2. Tukar dengan elemen terakhir.
  3. Keluarkan elemen terakhir.
  4. Memanaskan pokok.

Untuk Min Heap, algoritma di atas diubahsuai sehingga keduanya childNodeslebih kecil daripada currentNode.

Mengintip (Cari maksimum / min)

Operasi peek mengembalikan elemen maksimum dari Heap Maksimum atau elemen minimum dari Heap Min tanpa menghapus nod.

Untuk kedua Heap Max dan Min Heap

 kembali rootNode

Ekstrak-Maks / Min

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

Python, Java, C / C ++ Contoh

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

Aplikasi Struktur Data Tumpukan

  • Tumpukan digunakan semasa melaksanakan barisan keutamaan.
  • Algoritma Dijkstra
  • Isih timbunan

Artikel menarik...