🏔️ 9.1: Heap (Yığın) Veri Yapısı

# Heap indeks formülleri

def parent(i):
    """i'nin parent indeksini döndür"""
    return (i - 1) // 2

def left_child(i):
    """i'nin sol çocuk indeksini döndür"""
    return 2 * i + 1

def right_child(i):
    """i'nin sağ çocuk indeksini döndür"""
    return 2 * i + 2

# Heap dizisi
heap = [90, 85, 70, 40, 80, 30, 25, 10, 35, 75, 50, 20, 15, 5, 22]
print(f"Heap: {heap}")
print(f"Boyut: {len(heap)} eleman\n")

# Örnek hesaplamalar
for i in [0, 1, 4, 7]:
    print(f"=== İndeks {i} (değer: {heap[i]}) ===")

    p = parent(i)
    l = left_child(i)
    r = right_child(i)

    if i > 0:
        print(f"  Parent: indeks {p} → değer {heap[p]}")
    else:
        print(f"  Parent: Kök düğüm, parent yok")

    if l < len(heap):
        print(f"  Sol çocuk: indeks {l} → değer {heap[l]}")
    else:
        print(f"  Sol çocuk: yok (yaprak düğüm)")

    if r < len(heap):
        print(f"  Sağ çocuk: indeks {r} → değer {heap[r]}")
    else:
        print(f"  Sağ çocuk: yok")
    print()

import heapq

# ===== MIN HEAP TEMELLERİ =====
print("=== MIN HEAP İŞLEMLERİ ===\n")

# 1. Boş heap oluştur (sadece boş liste!)
heap = []

# 2. Insert / Ekleme - heappush(heap, item)
# Her ekleme sonrası heap özelliği korunur - O(log n)
print("İşlem 1: Insert (Ekleme)")
for val in [35, 10, 25, 5, 15, 30, 20]:
    heapq.heappush(heap, val)
    print(f"  {val} eklendi → heap: {heap}")

# 3. Peek / Find Min - En küçüğe bakma (silmeden)
# Sadece heap[0] okumak - O(1)
print(f"\nİşlem 2: Peek / Find Min (Gözetleme)")
print(f"  En küçük eleman: {heap[0]} ← Sadece bak, silme!")
print(f"  Heap değişmedi: {heap}")

# 4. Extract Min - En küçüğü çıkarma
# heappop(heap) - O(log n)
print(f"\nİşlem 3: Extract Min (Minimum Çıkarma)")
min_val = heapq.heappop(heap)
print(f"  Çıkarılan: {min_val}")
print(f"  Yeni min: {heap[0]}, Heap: {heap}")

# 5. Tüm elemanları sırayla çıkar
print("\nTüm elemanları çıkarıyoruz (sıralı çıkacak!):")
result = [min_val]  # İlk çıkanı da ekle
while heap:
    result.append(heapq.heappop(heap))

print(f"Çıkış sırası (küçükten büyüğe): {result}")

import heapq

# ===== HEAPIFY - Listeyi Heap'e Çevir =====
print("=== HEAPIFY ===")

# Normal liste
data = [35, 10, 25, 5, 15, 30, 20, 8, 12]
print(f"Orijinal liste: {data}")

# heapify() - Listeyi IN-PLACE heap'e çevirir
# Karmaşıklık: O(n) - tek tek eklemekten daha hızlı!
heapq.heapify(data)
print(f"Heapify sonrası: {data}")
print(f"Minimum: {data[0]}")

# ===== EN BÜYÜK/KÜÇÜK N ELEMAN =====
print("\n=== NLARGEST / NSMALLEST ===")

numbers = [64, 34, 25, 12, 22, 11, 90, 45, 78, 55]
print(f"Liste: {numbers}")

# nlargest(n, iterable) - En büyük n eleman
# nsmallest(n, iterable) - En küçük n eleman
print(f"En büyük 3: {heapq.nlargest(3, numbers)}")
print(f"En küçük 3: {heapq.nsmallest(3, numbers)}")

# ===== HEAPPUSHPOP ve HEAPREPLACE =====
print("\n=== ÖZEL FONKSİYONLAR ===")

heap = [5, 10, 15, 20]
heapq.heapify(heap)
print(f"Başlangıç heap: {heap}")

# heappushpop(heap, item): Önce ekle, sonra en küçüğü çıkar
# push ve pop'tan daha verimli!
result = heapq.heappushpop(heap, 3)
print(f"heappushpop(3): çıkan={result}, heap={heap}")

# heapreplace(heap, item): Önce en küçüğü çıkar, sonra ekle
result = heapq.heapreplace(heap, 25)
print(f"heapreplace(25): çıkan={result}, heap={heap}")

import heapq

class MaxHeap:
    """
    Python heapq min heap olduğu için,
    değerleri negatif yaparak max heap simüle ederiz.

    Mantık: -90 < -85 < -70 olduğu için,
    min heap'te -90 en üstte olur = aslında 90 en büyük!
    """

    def __init__(self):
        self._heap = []  # Alt çizgi: "private" değişken

    def push(self, val):
        """Değer ekle"""
        # Negatifini ekle
        heapq.heappush(self._heap, -val)

    def pop(self):
        """En büyük değeri çıkar ve döndür"""
        # Negatifi çıkar, pozitife çevir
        return -heapq.heappop(self._heap)

    def peek(self):
        """En büyük değere bak (silmeden)"""
        if self._heap:
            return -self._heap[0]
        return None

    def __len__(self):
        """len() fonksiyonu için"""
        return len(self._heap)

    def __bool__(self):
        """bool() dönüşümü için - boş mu?"""
        return len(self._heap) > 0

# Test
print("=== MAX HEAP KULLANIMI ===\n")

max_heap = MaxHeap()

# Eklemeler
for val in [35, 10, 90, 25, 5, 70]:
    max_heap.push(val)
    print(f"Push({val}) → En büyük: {max_heap.peek()}")

print(f"\nHeap boyutu: {len(max_heap)}")

# Çıkarmalar
print("\nÇıkarmalar (büyükten küçüğe):")
while max_heap:  # __bool__ sayesinde çalışır
    print(f"  Pop: {max_heap.pop()}")

import heapq

def heap_sort(arr):
    """
    Heap Sort - O(n log n) garantili

    Algoritma:
    1. Diziyi heap'e çevir - O(n)
    2. Tek tek çıkar (her çıkarma O(log n)) - O(n log n)

    Toplam: O(n log n)
    """
    # 1. Heap oluştur (in-place)
    heap = arr.copy()
    heapq.heapify(heap)  # O(n)

    # 2. Tek tek çıkar
    result = []
    while heap:
        result.append(heapq.heappop(heap))  # O(log n)

    return result

# Test
original = [64, 34, 25, 12, 22, 11, 90, 45]
print(f"Orijinal: {original}")

sorted_arr = heap_sort(original)
print(f"Sıralı:   {sorted_arr}")

# ===== HEAP SORT ÖZELLİKLERİ =====
print("\n" + "="*50)
print("HEAP SORT KARŞILAŞTIRMA")
print("="*50)

comparisons = [
    ("Zaman (her durum)", "O(n log n)", "Quick Sort en kötü O(n²)"),
    ("Alan", "O(1) in-place", "Merge Sort O(n) ek alan"),
    ("Stabilite", "❌ Stabil değil", "Merge Sort stabil"),
    ("Cache", "❌ Cache-unfriendly", "Quick Sort cache-friendly"),
    ("Pratikte", "Genelde yavaş", "Quick Sort tercih edilir"),
]

for ozellik, heap, karsilastirma in comparisons:
    print(f"\n{ozellik}:")
    print(f"  Heap Sort: {heap}")
    print(f"  Not: {karsilastirma}")

import heapq

def kth_largest(nums, k):
    """
    Dizideki k. en büyük elemanı bul.

    Yöntem 1: Sırala ve k. elemanı al - O(n log n)
    Yöntem 2: Min heap ile - O(n log k)

    Min heap kullanarak: k elemanlı heap tut,
    yeni eleman heap'in minimumundan büyükse değiştir.
    Sonunda heap'in kökü k. en büyük!
    """
    # k elemanlı min heap oluştur
    min_heap = nums[:k]
    heapq.heapify(min_heap)

    # Kalan elemanları işle
    for num in nums[k:]:
        if num > min_heap[0]:  # Heap'in minimumundan büyükse
            heapq.heapreplace(min_heap, num)  # Değiştir

    # Heap'in kökü k. en büyük
    return min_heap[0]

# Test
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(f"Dizi: {nums}")
print(f"{k}. en büyük: {kth_largest(nums, k)}")  # 5

nums2 = [3, 2, 3, 1, 2, 4, 5, 5, 6]
k2 = 4
print(f"\nDizi: {nums2}")
print(f"{k2}. en büyük: {kth_largest(nums2, k2)}")  # 4

import heapq

def merge_k_lists(lists):
    """
    K adet sıralı listeyi tek sıralı listede birleştir.

    Heap kullanarak O(n log k):
    - Her listeden bir eleman heap'e
    - Her seferinde minimum çıkar, o listeden sonrakini ekle
    """
    result = []

    # (değer, liste_indeksi, eleman_indeksi) tuple'ları
    # Heap tuple'ları ilk elemana göre karşılaştırır
    min_heap = []

    # Her listeden ilk elemanı ekle
    for i, lst in enumerate(lists):
        if lst:  # Boş liste kontrolü
            heapq.heappush(min_heap, (lst[0], i, 0))

    while min_heap:
        val, list_idx, elem_idx = heapq.heappop(min_heap)
        result.append(val)

        # O listeden sonraki eleman varsa ekle
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(min_heap, (next_val, list_idx, elem_idx + 1))

    return result

# Test
lists = [
    [1, 4, 5],
    [1, 3, 4],
    [2, 6]
]

print("Giriş listeleri:")
for i, lst in enumerate(lists):
    print(f"  Liste {i+1}: {lst}")

merged = merge_k_lists(lists)
print(f"\nBirleşik: {merged}")