Heap Kullanarak O(n log n) Sıralama
Heap Sort, heap veri yapısını kullanarak dizi sıralama algoritmasıdır. Temel fikir çok basit: Max Heap'te kök her zaman en büyük elemandır. O halde sürekli kökü alıp dizinin sonuna koyarsak, büyükten küçüğe sıralı bir dizi elde ederiz!
Heap Sort'un güzel yanı: Her durumda (best, average, worst) O(n log n) garantisi verir ve yerinde (in-place) çalışır - ek dizi gerekmez. Quick Sort gibi kötü durum riski yok!
Sonuç: Küçükten büyüğe sıralı dizi!
Heap sort algoritmasının çalışmasını adım adım izleyin!
Heap yapısının her adımda nasıl değiştiğini görün
def heapify(arr, n, i):
"""i'nci elemanı heap'te 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]
heapify(arr, n, largest)
def heap_sort(arr):
"""Heap sort algoritması"""
n = len(arr)
print("=== HEAP SORT ===\n")
print(f"Başlangıç dizisi: {arr}\n")
# ADIM 1: Build Max Heap
print("📦 ADIM 1: Build Max Heap")
print("-" * 40)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
print(f"Max Heap oluşturuldu: {arr}")
print(f"Kök (maksimum): {arr[0]}\n")
# ADIM 2: Extract max, tekrar tekrar
print("🔄 ADIM 2: Extract Max & Heapify")
print("-" * 40)
for i in range(n - 1, 0, -1):
# Root (en büyük) ile son elemanı swap
arr[0], arr[i] = arr[i], arr[0]
print(f"Swap root↔son: {arr}")
# Kalan heap'i düzelt (boyut = i)
heapify(arr, i, 0)
print(f" Heap: {arr[:i]} | Sıralı: {arr[i:]}")
print(f"\n✅ Sonuç: {arr}")
return arr
# Test
arr = [12, 11, 13, 5, 6, 7, 8, 3]
print(f"Orijinal: {arr}\n")
sorted_arr = heap_sort(arr.copy())
# Karmaşıklık
print("\n=== KARMAŞIKLIK ===")
print("Build Heap: O(n)")
print("n kez extract: n × O(log n) = O(n log n)")
print("Toplam: O(n log n)")| Algoritma | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Heap Sort | O(n log n) | O(n log n) | O(n log n) ✅ | O(1) | ❌ |
| Quick Sort | O(n log n) | O(n log n) | O(n²) ❌ | O(log n) | ❌ |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) ❌ | ✅ |