DAA - İkili Yığın

Birkaç yığın türü vardır, ancak bu bölümde ikili yığın tartışacağız. Birbinary heaptam bir ikili ağaca benzeyen bir veri yapısıdır. Yığın veri yapısı, aşağıda tartışılan sıralama özelliklerine uyar. Genel olarak, bir Yığın bir dizi ile temsil edilir. Bu bölümde, bir yığını temsil ediyoruzH.

Bir yığının öğeleri bir dizide depolandığından, başlangıç ​​dizini şu şekilde dikkate alınır: 1üst düğümün konumu ith eleman şurada bulunabilir: ⌊ i/2 ⌋. Sol çocuk ve sağ çocukith düğüm yerinde 2i ve 2i + 1.

Bir ikili yığın, bir max-heap veya a min-heap sipariş özelliğine göre.

Max-Yığın

Bu yığında, bir düğümün anahtar değeri, en yüksek alt öğenin anahtar değerinden büyük veya ona eşittir.

Bu nedenle H[Parent(i)] ≥ H[i]

Min-Yığın

Ortalama yığın olarak, bir düğümün anahtar değeri, en düşük alt öğenin anahtar değerinden küçüktür veya ona eşittir.

Bu nedenle H[Parent(i)] ≤ H[i]

Bu bağlamda, Max-Heap ile ilgili temel işlemler aşağıda gösterilmiştir. Öğelerin yığınlara yerleştirilmesi ve yığınlardan çıkarılması, öğelerin yeniden düzenlenmesini gerektirir. Bu nedenleHeapify işlevin çağrılması gerekiyor.

Dizi Gösterimi

Tam bir ikili ağaç, elemanlarını seviye sıralaması geçişi kullanarak depolayan bir dizi ile temsil edilebilir.

Bir dizi ile temsil edilecek bir yığın düşünelim (aşağıda gösterildiği gibi) H.

Başlangıç ​​endeksini şöyle düşünürsek 0, seviye sıralaması geçişi kullanılarak, öğeler aşağıdaki gibi bir dizide tutulur.

Index 0 1 2 3 4 5 6 7 8 ...
elements 70 30 50 12 20 35 25 4 8 ...

Bu bağlamda, yığın üzerindeki işlemler Max-Heap'e göre temsil edilmektedir.

Dizindeki bir elemanın ebeveyninin dizinini bulmak için iaşağıdaki algoritma Parent (numbers[], i) kullanıldı.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

Dizindeki bir öğenin sol alt öğesinin dizini i aşağıdaki algoritma kullanılarak bulunabilir, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

Dizindeki bir öğenin sağ alt dizini i aşağıdaki algoritma kullanılarak bulunabilir, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL