Heap: en küçük hep elinin altında

Bazen bir yığın sayıdan sürekli en küçüğünü almak, araya yenilerini eklemek istersin. Her seferinde listeyi baştan sıralamak pahalıdır; her seferinde min aramak da öyle. Heap tam bu iş içindir: ekleme de en küçüğü çıkarma da log n adımda biter.

1import heapq
2heap = []
3for v in [5, 1, 8, 3]:
4    heapq.heappush(heap, v)
5first = heapq.heappop(heap)   # 1
6second = heapq.heappop(heap)  # 3
7smallest_left = heap[0]       # 5

Python'da heap sıradan bir listedir; onu heap yapan heapq fonksiyonlarıdır. heappush ekler, heappop en küçüğü çıkarır, heap[0] çıkarmadan en küçüğe bakar. Elindeki listeyi tek seferde heap'e çevirmek için heapq.heapify(values) vardır.

n sayıyı heap'e koyup tek tek çıkarırsan sıralı gelirler; n ekleme ve n çıkarma, her biri log n: toplam n log n. Yani heap ile sıralama, iyi bir sıralamayla aynı sınıftadır. Heap'in asıl kazancı, sıralamanın tamamına ihtiyacın olmadığında ortaya çıkar.

Görevler