Insert, Delete, Heapify - Adım Adım
Yeni eleman ekle ve heap kuralını koru
Zaman: O(log n)
En büyük/küçük elemanı çıkar
Zaman: O(log n)
Diziyi heap'e dönüştür
Zaman: O(n)
Yeni eleman en sona eklenir, sonra yukarı doğru yüzdürülür (bubble up).
40 değerini heap'e ekleme adımlarını izleyin
Heap'te genelde sadece root silinir (max/min eleman). Silme sonrası heap kuralı korunmalı.
Root (en büyük) elemanı silme adımlarını izleyin
Rastgele bir diziyi heap'e dönüştürmek için tüm parent'ları aşağı batırırız.
Sezgisel düşünce: n eleman × log n = O(n log n) gibi görünür.
Ama: Alt seviyelerde çok eleman var ama az batırılıyor, üst seviyelerde az eleman var ama çok batırılıyor. Toplam: O(n)
Bu şaşırtıcı sonuç, heap sort'u çok verimli yapar!
def heapify_down(arr, n, i):
"""i indeksindeki elemanı aşağı batır"""
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: {i} ↔ {largest} → {arr}")
# Recursive olarak devam et
heapify_down(arr, n, largest)
def build_max_heap(arr):
"""Rastgele diziyi max heap'e çevir"""
n = len(arr)
print(f"Başlangıç dizisi: {arr}")
print("\n🔄 Heapify başlıyor...\n")
# Son parent'tan başla, geriye doğru git
# Son parent: (n//2 - 1)
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()
print(f"✅ Heap oluşturuldu: {arr}")
return arr
# Test
print("=== Heapify Demosu ===\n")
# Rastgele dizi
arr = [4, 10, 3, 5, 1, 8, 7]
print(f"Rastgele dizi (heap değil): {arr}")
# Heap'e çevir
heap = build_max_heap(arr.copy())
# Doğrulama
print("\n=== Doğrulama ===")
print(f"Root (en büyük): {heap[0]}")
print(f"Parent ≥ Children kuralı:")
for i in range(len(heap) // 2):
left = 2 * i + 1
right = 2 * i + 2
checks = f" {i} ({heap[i]})"
if left < len(heap):
status = "✅" if heap[i] >= heap[left] else "❌"
checks += f" ≥ L:{left} ({heap[left]}) {status}"
if right < len(heap):
status = "✅" if heap[i] >= heap[right] else "❌"
checks += f" ≥ R:{right} ({heap[right]}) {status}"
print(checks)Kendi heap'inizi oluşturun ve insert/delete operasyonlarını deneyin!
| İşlem | Zaman | Açıklama |
|---|---|---|
| Insert | O(log n) | Ağacın yüksekliği kadar yukarı çık |
| Delete (root) | O(log n) | Ağacın yüksekliği kadar aşağı in |
| Peek (root) | O(1) | Sadece indeks 0'a bak |
| Heapify (build) | O(n) | Diziyi heap'e çevir |
| Search | O(n) | Heap arama için optimize değil! |