Bir dizideki en büyük k elemanı (top-k) heap ile nasıl bulursunuz?
Cevap
Heap (priority queue), en küçük (min-heap) veya en büyük (max-heap) elemana O(1) erişim, ekleme ve kök çıkarmada O(log n) sağlayan, dizi üzerinde tutulan tam ikili ağaçtır.
Fikir
En büyük k elemanı bulmak için boyutu k olan bir min-heap tutulur. Heap'in kökü, şimdiye kadarki en büyük k elemanın en küçüğüdür. Yeni eleman kökten büyükse kök atılır, yeni eleman eklenir.
import heapq
def top_k(nums, k):
heap = []
for x in nums:
if len(heap) < k:
heapq.heappush(heap, x)
elif x > heap[0]:
heapq.heapreplace(heap, x) # pop + push tek adımda
return sorted(heap, reverse=True)
top_k([5, 1, 9, 3, 7, 8], 3) # [9, 8, 7]- Zaman:
O(n log k) - Bellek:
O(k)
Alternatifler
| Yöntem | Zaman | Not |
|---|---|---|
| Tümünü sırala | O(n log n) | En basit |
| Boyutu k min-heap | O(n log k) | Akan (stream) veride ideal |
| Tümünden heap kur, k kez pop | O(n + k log n) | heapify O(n) |
| Quickselect | Ortalama O(n) | Yerinde, en kötü O(n²) |
Python'da kısa yol heapq.nlargest(k, nums). "En sık geçen k eleman" varyasyonunda önce Counter ile frekanslar sayılır, sonra frekansa göre aynı teknik uygulanır.
Veri akış hâlinde geliyorsa ve tamamı belleğe sığmıyorsa boyutu k heap yaklaşımı tek uygun seçenektir.
İlgili Algoritmalar & Veri Yapıları soruları
- Binary search'ün zaman karmaşıklığı nedir ve neden?
- Two Sum: toplamı hedefe eşit olan iki elemanın indekslerini bulun.
- Bir parantez dizisinin geçerli olup olmadığını kontrol edin: "({[]})"
- Tek yönlü bağlı listeyi ters çevirin.
- BFS ve DFS arasındaki fark nedir? Hangisini ne zaman kullanırsınız?
- get ve put işlemleri O(1) olan bir LRU Cache tasarlayın.
Bu konuda başka bir soru biliyor musun?
Mülakatta karşılaştığın soruları ekle, onaylandıktan sonra yayına alınsın.