Yığın Veri Yapısı

Bu eğitimde, yığın veri yapısının ne olduğunu öğreneceksiniz. Ayrıca, C, C ++, Java ve Python'da yığın işlemlerinin çalışan örneklerini bulacaksınız.

Yığın veri yapısı, öbek özelliğini karşılayan tam bir ikili ağaçtır . Aynı zamanda ikili yığın olarak da adlandırılır .

Tam bir ikili ağaç, içinde özel bir ikili ağaçtır.

  • muhtemelen son hariç her seviye doldurulur
  • tüm düğümler olabildiğince solda

Heap Property, içinde bir düğümün özelliğidir.

  • (maks yığın için) her düğümün anahtarı her zaman alt düğümlerinden daha büyüktür ve kök düğümün anahtarı diğer tüm düğümler arasında en büyüğüdür;
  • Her bir düğümün (min heap için) anahtarı her zaman alt düğümden / düğümlerden daha küçüktür ve kök düğümün anahtarı diğer tüm düğümler arasında en küçük olanıdır.

Yığın İşlemleri

Bir yığın üzerinde gerçekleştirilen önemli işlemlerden bazıları, algoritmalarıyla birlikte aşağıda açıklanmıştır.

Yığınla

Heapify, ikili bir ağaçtan bir yığın veri yapısı oluşturma işlemidir. Min-Heap veya Max-Heap oluşturmak için kullanılır.

  1. Girdi dizisi olsun
  2. Diziden tam bir ikili ağaç oluşturun
  3. Dizini tarafından verilen yaprak olmayan düğümün ilk dizininden başlayın n/2 - 1.
  4. Geçerli öğeyi iolarak ayarla largest.
  5. Sol çocuk endeksi tarafından verilir 2i + 1ve sağ çocuk tarafından verilir 2i + 2.
    Eğer leftChilddaha büyüktür currentElement(en yani eleman ithindeksi), set leftChildIndexbüyük olarak.
    Eğer rightChildiçinde eleman daha büyüktür largestayarlayın rightChildIndexolarak largest.
  6. Takas largestilecurrentElement
  7. Alt ağaçlar da yığılıncaya kadar 3-7 arasındaki adımları tekrarlayın.

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)

Max-Heap oluşturmak için:

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

Min-Heap için, hem leftChildve rightChildtüm düğümler için üst öğeden daha küçük olmalıdır.

Öbeğe Öğe Ekleme

Max Heap'e ekleme için algoritma

 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. Yeni öğeyi ağacın sonuna ekleyin.
  2. Ağacı yığınlayın.

Min Heap için, yukarıdaki algoritma parentNode, her zaman daha küçük olacak şekilde değiştirilir newNode.

Öğeyi Yığından Sil

Max Heap'te silme algoritması

 If nodeToBeDeleted is the leafNode remove the node Else swap nodeToBeDeleted with the lastLeafNode remove noteToBeDeleted heapify the array
  1. Silinecek öğeyi seçin.
  2. Son elementle değiştirin.
  3. Son öğeyi kaldırın.
  4. Ağacı yığınlayın.

Min Heap için, yukarıdaki algoritma, her ikisinin childNodesde daha küçük olması için değiştirilmiştir currentNode.

Göz at (Maksimum / dakika bul)

Peek işlemi, düğümü silmeden Max Heap'ten maksimum elementi veya Min Heap'ten minimum elementi döndürür.

Hem Max heap hem de Min Heap için

 rootNode döndür

Ekstrakt-Maks / Min

Extract-Max, bir Max Heap'ten çıkardıktan sonra maksimum değeri olan düğümü döndürürken Extract-Min, Min Heap'ten çıkardıktan sonra düğümü minimum ile döndürür.

Python, Java, C / C ++ Örnekleri

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

Yığın Veri Yapısı Uygulamaları

  • Heap, bir öncelik kuyruğu uygulanırken kullanılır.
  • Dijkstra Algoritması
  • Yığın Sıralama

Ilginç makaleler...