Heap Veri Yapısıyla Çözülen Klasik Problemler
Bir nums dizisi ve k sayısı verildiğinde, dizideki en büyük k elemanı döndürün.
heapq.nlargest() fonksiyonu doğrudan kullanılabilir. Ya da min heap ile sadece k eleman tutarak çözün.
import heapq
def top_k_elements(nums, k):
"""En büyük k elemanı döndür - O(n log k)"""
# Min heap ile sadece k eleman tut
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
# k'dan fazla varsa en küçüğü çıkar
if len(min_heap) > k:
heapq.heappop(min_heap)
# Heap'teki k eleman = en büyük k eleman
return sorted(min_heap, reverse=True)
def top_k_simple(nums, k):
"""Basit çözüm - heapq.nlargest kullan"""
return heapq.nlargest(k, nums)
# Test
nums = [3, 1, 5, 12, 2, 11, 8, 9]
k = 3
print(f"Dizi: {nums}")
print(f"k = {k}")
print(f"\nEn büyük {k} eleman (heap):", top_k_elements(nums, k))
print(f"En büyük {k} eleman (nlargest):", top_k_simple(nums, k))Bir dizide k. en büyük elemanı bulun. (LeetCode #215)
import heapq
def find_kth_largest(nums, k):
"""K. en büyük elemanı bul - O(n log k)"""
# Min heap ile k eleman tut
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap)
# Heap root = k. en büyük
return min_heap[0]
def find_kth_largest_simple(nums, k):
"""Basit: heapq.nlargest kullan"""
return heapq.nlargest(k, nums)[-1]
# Test
test_cases = [
([3, 2, 1, 5, 6, 4], 2), # 5
([3, 2, 3, 1, 2, 4, 5, 5, 6], 4), # 4
([1], 1), # 1
]
for nums, k in test_cases:
result = find_kth_largest(nums, k)
print(f"nums={nums}, k={k} → {k}. en büyük: {result}")K adet sıralı liste verildiğinde, bunları tek bir sıralı listede birleştirin. (LeetCode #23)
import heapq
def merge_k_sorted(lists):
"""K sıralı listeyi birleştir - O(n log k)"""
min_heap = []
result = []
# Her listenin ilk elemanını heap'e ekle
for i, lst in enumerate(lists):
if lst: # Boş liste değilse
# (değer, liste_index, eleman_index)
heapq.heappush(min_heap, (lst[0], i, 0))
while min_heap:
val, list_idx, elem_idx = heapq.heappop(min_heap)
result.append(val)
# Bu listede 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}")
print(f"\nBirleştirilmiş: {merge_k_sorted(lists)}")
# Edge case test
print(f"\nBoş listelerle: {merge_k_sorted([[], [1], [2,3]])}")2D düzlemde noktalar verildiğinde, orijine (0,0) en yakın k noktayı bulun. (LeetCode #973)
import heapq
def k_closest(points, k):
"""Orijine en yakın k noktayı bul - O(n log k)"""
# Max heap (negatif uzaklık) ile k eleman tut
max_heap = []
for x, y in points:
dist = x*x + y*y # Kare uzaklık (sqrt gerekmez)
# Max heap için negatif kullan
heapq.heappush(max_heap, (-dist, [x, y]))
# k'dan fazla varsa en uzağı çıkar
if len(max_heap) > k:
heapq.heappop(max_heap)
return [point for _, point in max_heap]
def k_closest_simple(points, k):
"""Alternatif: nsmallest ile"""
return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)
# Test
points = [[1, 3], [-2, 2], [5, 8], [0, 1]]
k = 2
print(f"Noktalar: {points}")
print(f"k = {k}")
print(f"\nEn yakın {k} nokta: {k_closest(points, k)}")
# Uzaklıkları göster
print("\nTüm uzaklıklar:")
for x, y in points:
dist = (x**2 + y**2) ** 0.5
print(f" ({x}, {y}) → {dist:.2f}")Sürekli gelen sayıların medyanını her an hesaplayın. (LeetCode #295)
import heapq
class MedianFinder:
def __init__(self):
# small = max heap (negatif), large = min heap
self.small = [] # Küçük yarı
self.large = [] # Büyük yarı
def addNum(self, num):
# Önce small'a ekle (max heap = negatif)
heapq.heappush(self.small, -num)
# small'ın max'ı large'ın min'inden büyükse aktar
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 (small en fazla 1 fazla olabilir)
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 findMedian(self):
if len(self.small) > len(self.large):
return -self.small[0]
return (-self.small[0] + self.large[0]) / 2
# Test
mf = MedianFinder()
numbers = [5, 15, 1, 3, 2, 8, 7, 9]
print("Sayılar ekleniyor:")
for num in numbers:
mf.addNum(num)
median = mf.findMedian()
print(f" Ekle {num:2d} → Medyan: {median}")
print(f"\nSmall heap (küçük yarı): {[-x for x in mf.small]}")
print(f"Large heap (büyük yarı): {mf.large}")Görevler dizisi ve n cooldown süresi verildiğinde, tüm görevleri tamamlamak için minimum süreyi bulun. Aynı görev arasında en az n birim beklenmeli. (LeetCode #621)
import heapq
from collections import Counter, deque
def least_interval(tasks, n):
"""Minimum süreyi hesapla - O(m) m = toplam süre"""
# Görev sayılarını hesapla
count = Counter(tasks)
# Max heap (negatif sayılar)
max_heap = [-c for c in count.values()]
heapq.heapify(max_heap)
# Cooldown queue: (count, available_time)
queue = deque()
time = 0
while max_heap or queue:
time += 1
if max_heap:
cnt = 1 + heapq.heappop(max_heap) # +1 çünkü negatif
if cnt: # Hala görevi varsa cooldown'a ekle
queue.append((cnt, time + n))
# Cooldown bitti mi kontrol et
if queue and queue[0][1] == time:
heapq.heappush(max_heap, queue.popleft()[0])
return time
# Test
test_cases = [
(["A","A","A","B","B","B"], 2),
(["A","A","A","B","B","B"], 0),
(["A","A","A","A","A","A","B","C","D","E","F","G"], 2),
]
for tasks, n in test_cases:
result = least_interval(tasks, n)
print(f"tasks={tasks}")
print(f"n={n} → Minimum süre: {result}")
print()Taş ağırlıkları verildiğinde, her turda en ağır iki taşı çarpıştır. Eşit ağırlıksa ikisi de yok olur, farklıysa fark kalır. Son taşın ağırlığını bulun. (LeetCode #1046)
import heapq
def last_stone_weight(stones):
"""Son taşın ağırlığını bul - O(n log n)"""
# Max heap (negatif değerler)
max_heap = [-s for s in stones]
heapq.heapify(max_heap)
while len(max_heap) > 1:
# En ağır iki taşı al
stone1 = -heapq.heappop(max_heap)
stone2 = -heapq.heappop(max_heap)
print(f" {stone1} vs {stone2}", end="")
if stone1 != stone2:
diff = stone1 - stone2
heapq.heappush(max_heap, -diff)
print(f" → {diff} kalır")
else:
print(" → ikisi de yok olur")
return -max_heap[0] if max_heap else 0
# Test
stones = [2, 7, 4, 1, 8, 1]
print(f"Taşlar: {stones}\n")
print("Çarpışmalar:")
result = last_stone_weight(stones)
print(f"\n✅ Son taş ağırlığı: {result}")Toplantı aralıkları verildiğinde, minimum kaç oda gerektiğini bulun. (LeetCode #253)
import heapq
def min_meeting_rooms(intervals):
"""Minimum oda sayısını bul - O(n log n)"""
if not intervals:
return 0
# Başlangıç zamanına göre sırala
intervals.sort(key=lambda x: x[0])
# Min heap: aktif odaların bitiş zamanları
rooms = []
for start, end in intervals:
# En erken biten oda boşaldı mı?
if rooms and rooms[0] <= start:
heapq.heappop(rooms) # Eski odayı boşalt
# Bu toplantı için oda ayır
heapq.heappush(rooms, end)
return len(rooms)
# Test
test_cases = [
[[0, 30], [5, 10], [15, 20]], # 2 oda
[[7, 10], [2, 4]], # 1 oda
[[0, 10], [5, 15], [10, 20]], # 2 oda
]
for intervals in test_cases:
result = min_meeting_rooms(intervals)
print(f"Toplantılar: {intervals}")
print(f"Minimum oda: {result}\n")| Top-K Problems | En büyük/küçük K eleman |
| Kth Element | K. sıradaki eleman |
| Merge K Lists | K sıralı yapıyı birleştir |
| Scheduling | Task/meeting planlama |
| Stream Data | Akan veride medyan/top-K |