Python Heap / Priority Queue

Heap / Priority Queue Nedir?

Heap, her düğümün çocuklarından büyük (veya küçük) olduğu özel bir binary tree veri yapısıdır. En yaygın kullanımı priority queue: en yüksek (veya en düşük) öncelikli elemanın O(1) veya O(log n) sürede alınması. Python'da heapq modülü min-heap implementasyonu sağlar; max-heap için değerlerin negatifi kullanılır.

Mülakatlarda en sık sorulan heap soruları: K'th largest/smallest elemanı bul, top K frequent, median maintenance (veri akışından medyan tut), Dijkstra'nın kısa yol algoritması. Heap'in asıl gücü, sıralanmamış bir veri yapısından en iyi/en kötü elemanı sürekli çekme işleminde ortaya çıkar.

import heapq

# Min-heap oluşturma
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)

# En küçük elemanı çek (O(log n))
print(heapq.heappop(heap))   # 1
print(heap)                   # [3, 5, 7]

# Max-heap trick: negatif değerler
maxh = []
heapq.heappush(maxh, -5)
heapq.heappush(maxh, -1)
heapq.heappush(maxh, -3)
print(-heapq.heappop(maxh))   # 5

# n largest / n smallest
nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
print(heapq.nlargest(3, nums))   # [9, 6, 5]
print(heapq.nsmallest(3, nums))  # [1, 1, 2]

Heap Ne Zaman Kullanılır?

Heap, en iyi/en kötü elemanı sürekli çekmen gereken durumlarda idealdir. Sıralı erişim gerekmiyorsa (O(1) peek + O(log n) pop), Dijkstra ve A* gibi graf algoritmalarında, median maintenance (iki heap'le çalışan trick), task scheduler (en yüksek öncelikli görev önce), ve K'th largest problemlerinde kullanılır. Sıralı iterasyon gerekirse heap yerine sorted set veya balanced BST tercih edilir.