🌳 7.7: Heap Sort (Yığın Sıralaması)

# ====================================
# HEAP SORT ALGORİTMASI
# ====================================

def heapify(arr, n, i):
    """
    i indeksindeki düğümü max-heap özelliğine uygun hale getir.
    
    Parametreler:
    - arr: Dizi
    - n: Heap boyutu (sıralama sırasında azalır)
    - i: Heapify yapılacak düğüm indeksi
    """
    largest = i          # Başlangıçta kök en büyük varsayılır
    left = 2 * i + 1     # Sol çocuk indeksi
    right = 2 * i + 2    # Sağ çocuk indeksi
    
    # Sol çocuk daha büyükse
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # Sağ çocuk daha büyükse
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # En büyük kök değilse swap yap ve recursive heapify
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        print(f"  Swap: arr[{i}]={arr[largest]} ↔ arr[{largest}]={arr[i]}")
        heapify(arr, n, largest)

def heap_sort(arr):
    """
    Heap Sort Ana Fonksiyonu
    
    Zaman Karmaşıklığı: O(n log n) - Her durumda
    Alan Karmaşıklığı: O(1) - In-place
    Stable: Hayır
    """
    n = len(arr)
    
    # AŞAMA 1: Build Max-Heap
    print("=" * 50)
    print("AŞAMA 1: Build Max-Heap")
    print("=" * 50)
    
    # Son yaprak olmayan düğümden başla: n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        print(f"\nHeapify index {i} (değer: {arr[i]})")
        heapify(arr, n, i)
        print(f"Dizi: {arr}")
    
    print(f"\n✅ Max-Heap oluşturuldu: {arr}")
    
    # AŞAMA 2: Sıralama - Kökü sona taşı
    print("\n" + "=" * 50)
    print("AŞAMA 2: Sıralama (Extract Max)")
    print("=" * 50)
    
    for i in range(n - 1, 0, -1):
        # Kökü (en büyük) sona taşı
        arr[0], arr[i] = arr[i], arr[0]
        print(f"\nSwap root({arr[i]}) ↔ arr[{i}]({arr[0]})")
        
        # Yeni kökte heapify (boyut azaltılmış heap için)
        heapify(arr, i, 0)
        print(f"Dizi: {arr[:i]} | Sıralı: {arr[i:]}")
    
    return arr

# ============ TEST ============
print("🌳 HEAP SORT")
print("=" * 50)

dizi = [4, 10, 3, 5, 1]
print(f"Başlangıç: {dizi}\n")

heap_sort(dizi)
print(f"\n🎉 Sonuç: {dizi}")

import heapq

# heapq ile sıralama
dizi = [4, 10, 3, 5, 1]
print(f"Orijinal: {dizi}")

# Yöntem 1: heapify + pop
heap = dizi.copy()
heapq.heapify(heap)  # O(n)
print(f"Min-Heap: {heap}")

sirali = []
while heap:
    sirali.append(heapq.heappop(heap))
print(f"Sıralı: {sirali}")

# Yöntem 2: nsmallest / nlargest
print(f"\nEn küçük 3: {heapq.nsmallest(3, dizi)}")
print(f"En büyük 3: {heapq.nlargest(3, dizi)}")

# Priority Queue olarak kullanım
print("\n--- Priority Queue ---")
pq = []
heapq.heappush(pq, (3, "Görev C"))
heapq.heappush(pq, (1, "Görev A"))
heapq.heappush(pq, (2, "Görev B"))

while pq:
    priority, task = heapq.heappop(pq)
    print(f"  Öncelik {priority}: {task}")