🔢 9.3: Heap Sort

def heapify(arr, n, i):
    """i'nci elemanı heap'te aşağı batır"""
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    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ıç: {arr}\n")

    # ADIM 1: Build Max Heap (Max Heap Oluştur)
    print("ADIM 1: Build Max Heap (Max Heap Oluştur)")
    print("-" * 40)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    print(f"Max Heap: {arr}")
    print(f"Root (en büyük): {arr[0]}\n")

    # ADIM 2: Extract elemanları tek tek (Elemanları Çıkar ve Sırala)
    print("ADIM 2: Extract & Sort (Çıkar ve Sırala)")
    print("-" * 40)

    for i in range(n - 1, 0, -1):
        # Root'u (en büyük) sona taşı
        arr[0], arr[i] = arr[i], arr[0]
        print(f"Swap: 0 ↔ {i} → {arr}")
        print(f"  Sıralanmış kısım: {arr[i:]} ✅")

        # Kalan heap'i düzelt
        heapify(arr, i, 0)
        print(f"  Heapify sonrası: {arr[:i]} (heap) + {arr[i:]} (sıralı)")
        print()

    print(f"✅ Sıralama tamamlandı: {arr}")
    return arr

# Test
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = heap_sort(arr.copy())

# Doğrulama
print("\n=== Doğrulama ===")
print(f"Sıralı mı? {sorted_arr == sorted(sorted_arr)}")
print(f"Sonuç: {sorted_arr}")