Heap ve Top K

Nasıl düşünülür

Heap ilgi sınırını tutar. Top K en büyük için boyut K min-heap güncel kazananları saklar; kök en zayıf kazanandır. Akışlarda iki heap alt/üst yarıyı dengeleyerek medyan verir.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Top K	Boyut K min-heap	Yeni daha iyiyse kökü at
K-yollu birleştirme	Başların min-heap’i	Aynı listeden sonrakini push
Medyan	Max-heap + min-heap	Boyutları dengele

Karmaşıklık temeli

Top-K için tipik O(n log k); ekleme/pop O(log n). Alan O(k) veya O(n).

Şablondan probleme

1. Netleştir: K en büyük, K en küçük veya K sık mı?
2. Kökün atmaya hazır olduğun eleman olacağı heap yönelimini seç.
3. Elemanları işle; uygunsa heap boyutu ≤ K kalsın.
4. Heap’i cevap formatına çıkar veya dönüştür.

/** Heap / top-K template: kth largest via min-heap of size k. */
export function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = [];
  for (const x of nums) {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap[0]!;
}

/** Heap / top-K template: kth largest via min-heap of size k. */
export function findKthLargest(nums: number[], k: number): number {
  const heap: number[] = [];
  for (const x of nums) {
    heap.push(x);
    heap.sort((a, b) => a - b);
    if (heap.length > k) heap.shift();
  }
  return heap[0]!;
}