Yaprakları hariç tüm düzeyleri dolu olan, max ve min olmak üzere iki çeşidi olan ağaçlardır. Heap ağaçları binary tree’dir fakat binary search tree değildir. Max heap ağacında her node’un değeri çocuklarından büyük, min heap ağacında ise her node’un değeri çocuklarından küçüktür.
Heap Tree Creation
Bir diziyi bir “heap tree” veri yapısına dönüştürme işlemine heapify denilmektedir.
Bir diziden max veya min heap tree oluşturulmak istendiğinde ilk olarak tüm elemanlar sırasıyla seviyeye göre dizilir. Sonrasında en aşağıdan başlanarak parent node’unun değeri yaprakarından küçük veya büyük olanıyla değiştirilir. Bu işleme swap denir. Bu işlem kök node’a kadar devam ettirilir.
[3, 14, 8, 11, 5, 6, 10, 9] sayı dizisinden maksimum heap tree oluşturalım.
İlk olarak elemanları seviyeye göre sırasıyla yerleştirelim.
Sonrasında en aşağıdan başlayarak swap işlemlerini yapalım.
11 node’u için, tek çocuğu olan 9’dan büyük. İşlem yapmamıza gerek yok. 14 node’u yine iki çocuğu 11 ve 5’ten büyük işlem yapmamıza gerek yok. 8 node’unda ise sol çocuğu olan 10 daha büyük. Burada ikisinin yerini değiştirmemeniz yani swap gerçekleştirmeliyiz.
3 node’unun iki çocuğu da kendisinden büyük. Daha büyük olan çocuğuyla swap yapalım.
Kök node’u içinde işlemi gerçekleştirdik peki tüm işlemler bitti mi? Hayır. Çünkü, her node çocuklarından büyük olması gerekiyor. Fakat 3 node’u iki çocuğundan da küçük. 11 node’u ile yer değiştirelim.
3 node’unu yer 11 ile yer değiştirdik fakat bu sefer de yeni çocuğu olan 9 dan küçük. 3 ve 9 için swap işlemini uygulayalım.
Ve heap tree’yi oluşturduk.
Heap Tree Insertion
Heap tree’de eleman eklenmek istendiğinde son yapraktan sonra bir yaprak oluşturulur ve eleman buraya eklenir. Gerekirse swap işlemleri yapılır.
Aşağıdaki minimum heap tree’ye “10” elemanını ekleyelim.
10 elemanı en sonra 12 node’unun çocuğu olarak eklenir.
10 parent’ı 12’den daha küçük olduğu için swap işlemi uygulanır.
Tüm node’lar çocuklarından küçük olduğu için başka swap işlemine gerek kalmaz ve ekleme işlemi tamamlanır.
Heap Tree Deletion
Silme işleminde, silinecek eleman ile en sonda bulunan yaprak node’un elemanı yer değiştirir. Daha sonra artık yaprakta olan silinecek elemanın node’u ağaçtan kaldırılır. Sonrasında ağacın maksimum veya minimum olma durumuna göre swap işlemleri yapılır.
Aşağıdaki maksimum heap ağacından 11 elemanını silelim.
Öncelikle en sonda bulunan yaprak ile 11 node’unu yer değiştirelim ve yaprağa geçen silinecek ağaçtan kaldıralım.
Şimdi en aşağıdan başlayarak her node’un değerinin çocuklarından büyük olmasını sağlayalım. 3 node’unun çocukları kendisinden daha büyük. 3 ile 9 node’una swap işlemi uygulayalım.
Ve silme işlemi tamamlandı.