Insert, Delete, Heapify - Adım Adım Görselleştirme
Yeni eleman ekle → Heapify Up
Zaman: O(log n)
Kökü çıkar → Heapify Down
Zaman: O(log n)
Diziyi heap'e dönüştür
Zaman: O(n) 🎉
Heap'e yeni eleman eklemek için önce elemanı ağacın en sonuna (en alt seviyede, soldan ilk boş yere) ekliyoruz. Ama bu noktada heap özelliği bozulmuş olabilir - yeni eleman parent'ından büyük olabilir!
Bu sorunu çözmek için Heapify Up (yukarı yüzdürme / bubble up) işlemi yapıyoruz: Yeni elemanı parent'ı ile karşılaştırıp, gerekirse swap yaparak yukarı taşıyoruz. Köke ulaşana veya parent'tan küçük olana kadar devam ediyoruz.
(i-1) // 2 formülü ile hesaplaNeden O(log n)? En kötü durumda, eleman kökten yapraklara kadar tırmanır. Ağacın yüksekliği log₂(n) olduğu için en fazla log n swap yapılır.
Mevcut heap'e yeni değer ekleyin ve Heapify Up izleyin
Heap'te silme işlemi biraz farklı çalışır: sadece kök silinebilir. Neden? Çünkü heap'in amacı zaten en büyük (max heap) veya en küçük (min heap) elemana hızlı erişim sağlamak. Ortadaki bir elemanı silmek heap'in temel kullanım senaryosu değil.
Peki kökü nasıl siliyoruz? Direkt köküi silsek ağaç yapısı bozulur! Bunun yerine şu trick kullanılır:
heap[0] = heap[n-1]Neden O(log n)? Insert'e benzer şekilde, en kötü durumda kökten yaprağa kadar iner. Yükseklik log₂(n) olduğu için O(log n).
Kökü (en büyük) silme ve Heapify Down izleyin
Elimizde rastgele sıralı bir dizi var ve bunu heap'e çevirmek istiyoruz. Bunun iki yolu var:
Build Heap algoritmasında, son parent'tan başlayarak (indeks n/2 - 1) geriye doğru her parent'a heapify_down uygularız. Yapraklar zaten tek başlarına geçerli heap oldukları için onları atlıyoruz.
İlk bakışta n eleman × log n heapify = O(n log n) gibi görünür. Ama:
Başka bir bakış açısı: Her düğüm en fazla ağacın yüksekliği kadar hareket eder, ama çoğu düğüm (yapraklar) hiç hareket etmez!
def heapify_down(arr, n, i):
"""i indeksindeki elemanı aşağı batır (Max Heap)"""
largest = i
left = 2 * i + 1
right = 2 * i + 2
# Sol child büyük mü?
if left < n and arr[left] > arr[largest]:
largest = left
# Sağ child daha büyük mü?
if right < n and arr[right] > arr[largest]:
largest = right
# Swap gerekli mi?
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
print(f" Swap: indeks {i} ({arr[largest]}) ↔ indeks {largest} ({arr[i]})")
# Recursive olarak devam et
heapify_down(arr, n, largest)
def build_max_heap(arr):
"""Rastgele diziyi max heap'e çevir - O(n)"""
n = len(arr)
print(f"Başlangıç dizisi: {arr}\n")
# Son parent'tan başla: (n//2 - 1)
# Yapraklar zaten heap özelliğini sağlıyor
start = n // 2 - 1
for i in range(start, -1, -1):
print(f"🔽 Parent[{i}] = {arr[i]} batırılıyor...")
heapify_down(arr, n, i)
print(f" Ara durum: {arr}")
print()
return arr
# Test
print("=== BUILD MAX HEAP ===\n")
arr = [4, 10, 3, 5, 1, 8, 7]
print(f"📋 Orijinal (rastgele) dizi: {arr}")
print("=" * 40)
heap = build_max_heap(arr.copy())
print("=" * 40)
print(f"✅ Sonuç (Max Heap): {heap}")
print(f"🔝 Kök (maksimum): {heap[0]}")
# Doğrulama
print("\n=== DOĞRULAMA ===")
print("Her parent ≥ children olmalı:")
for i in range(len(heap) // 2):
left = 2 * i + 1
right = 2 * i + 2
msg = f" [{i}]={heap[i]}"
if left < len(heap):
check = "✅" if heap[i] >= heap[left] else "❌"
msg += f" ≥ L[{left}]={heap[left]} {check}"
if right < len(heap):
check = "✅" if heap[i] >= heap[right] else "❌"
msg += f" ≥ R[{right}]={heap[right]} {check}"
print(msg)Kendi heap'inizi oluşturun ve operasyonları deneyin!
| İşlem | Zaman | Açıklama |
|---|---|---|
| Insert | O(log n) | Sona ekle + yukarı yüzdür |
| Delete (root) | O(log n) | Son elemanı köke taşı + aşağı batır |
| Peek (root) | O(1) | Sadece indeks 0'a bak |
| Build Heap | O(n) | Diziyi heap'e çevir (heapify) |
| Search | O(n) | Heap arama için optimize değil! |
(i-1)//2, Left: 2i+1, Right: 2i+2