🌍 9.6: Heap Gerçek Örnekler

import heapq

def top_k_largest(nums, k):
    """En büyük k elemanı bul - O(n log k)"""
    # Min heap kullan (boyut k)
    min_heap = []
    
    for num in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    
    return sorted(min_heap, reverse=True)

# Test
nums = [3, 2, 1, 5, 6, 4, 7, 8, 9]
k = 3

print(f"Liste: {nums}")
print(f"En büyük {k} eleman: {top_k_largest(nums, k)}")

# heapq ile daha kolay
print(f"\nheapq.nlargest: {heapq.nlargest(k, nums)}")

# Performans karşılaştırma
import time

big_list = list(range(100000, 0, -1))  # 100,000 eleman

# Yöntem 1: Sıralama
start = time.time()
result1 = sorted(big_list, reverse=True)[:10]
time1 = time.time() - start

# Yöntem 2: Heap
start = time.time()
result2 = heapq.nlargest(10, big_list)
time2 = time.time() - start

print(f"\n=== 100K elemanda en büyük 10 ===")
print(f"Sıralama: {time1*1000:.2f} ms")
print(f"Heap: {time2*1000:.2f} ms")
print(f"Heap {time1/time2:.1f}x daha hızlı!")

import heapq

def merge_k_sorted(lists):
    """K tane sıralı listeyi birleştir"""
    heap = []
    result = []
    
    # Her listeden ilk elemanı heap'e ekle
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    
    # Heap'ten tek tek çıkar
    while heap:
        val, list_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # Bu listeden bir sonraki elemanı ekle
        if elem_idx + 1 < len(lists[list_idx]):
            next_val = lists[list_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
    
    return result

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

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

merged = merge_k_sorted(lists)
print(f"\nBirleştirilmiş: {merged}")
print(f"Sıralı mı? {merged == sorted(merged)}")

import heapq

class Task:
    def __init__(self, name, priority, duration):
        self.name = name
        self.priority = priority  # Düşük = yüksek öncelik
        self.duration = duration
    
    def __lt__(self, other):
        return self.priority < other.priority
    
    def __repr__(self):
        return f"{self.name}(P{self.priority}, {self.duration}s)"

def schedule_tasks(tasks):
    """Görevleri öncelik sırasına göre çalıştır"""
    heap = []
    
    # Tüm görevleri heap'e ekle
    for task in tasks:
        heapq.heappush(heap, task)
    
    print("=== Görev Zamanlayıcı ===\n")
    total_time = 0
    
    while heap:
        task = heapq.heappop(heap)
        print(f"⏰ Zaman {total_time}s: {task.name} başladı")
        print(f"   Öncelik: {task.priority}, Süre: {task.duration}s")
        total_time += task.duration
        print(f"   {task.name} tamamlandı ({total_time}s)\n")
    
    print(f"✅ Tüm görevler {total_time}s'de tamamlandı")

# Test
tasks = [
    Task("Video oynat", 5, 3),
    Task("Sistem güncelle", 2, 10),
    Task("Virüs tara", 3, 8),
    Task("Güvenlik duvarı", 1, 2),  # En yüksek öncelik!
    Task("Email senkronize", 4, 5)
]

print("Gelen görevler:")
for task in tasks:
    print(f"  {task}")

print()
schedule_tasks(tasks)

import heapq

class MedianFinder:
    """2 heap ile medyan bul (akış halinde)"""
    
    def __init__(self):
        self.small = []  # Max heap (negatif)
        self.large = []  # Min heap
    
    def add_num(self, num):
        """Yeni sayı ekle"""
        # Önce small'a ekle (max heap)
        heapq.heappush(self.small, -num)
        
        # small'ın max'ı large'ın min'inden küçük olmalı
        if self.small and self.large and (-self.small[0] > self.large[0]):
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        # Boyutları dengele
        if len(self.small) > len(self.large) + 1:
            val = -heapq.heappop(self.small)
            heapq.heappush(self.large, val)
        
        if len(self.large) > len(self.small):
            val = heapq.heappop(self.large)
            heapq.heappush(self.small, -val)
    
    def find_median(self):
        """Medyanı bul"""
        if len(self.small) > len(self.large):
            return -self.small[0]
        else:
            return (-self.small[0] + self.large[0]) / 2.0

# Test
mf = MedianFinder()
nums = [5, 15, 1, 3, 8, 7, 9, 10, 20]

print("=== Akış Halinde Medyan ===\n")

for num in nums:
    mf.add_num(num)
    median = mf.find_median()
    print(f"Ekle {num:2d} → Medyan: {median}")