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 i^th eleman şurada bulunabilir: ⌊ i/2 ⌋. Sol çocuk ve sağ çocuki^th 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