유형별 정리/자료구조
자료구조O(n log k)

상위 K개·K번째 수 — 우선순위 큐

크기 K 힙으로 상위 K개만 유지해요. 전체 정렬(O(n log n))보다 빨라요.

이럴 때 써요

  • 가장 큰(작은) K개, 또는 K번째로 큰 수를 구할 때
  • 빈도 상위 K개처럼 '많이 나온 순서'가 필요할 때
  • 전체를 정렬하기엔 데이터가 크고, K는 작을 때
  • 값이 하나씩 흘러 들어오는 스트림에서 실시간으로 상위/중앙값을 유지할 때

개념

상위 K개만 필요한데 전체를 정렬하면 O(n log n) 이라 아까워요. 크기 K짜리 최소 힙을 유지하면 O(n log k) 로 줄어요. 힙에 하나 넣고, 크기가 K를 넘으면 가장 작은 걸 하나 버려요. 그렇게 끝까지 훑으면 힙엔 가장 큰 K개만 남아요.왜 하필 최소 힙일까요? 최소 힙은 루트가 가장 작은 값이에요. 즉 힙에 든 K개 중 최솟값이 루트에 있어요. 새 값이 이 루트보다 크면 K개 안에 들 자격이 있으니 루트를 버리고 넣어요. 그래서 'K번째로 큰 수'는 다 훑은 뒤의 루트가 바로 답이에요.
"[5, 1, 8, 3, 9] 에서 가장 큰 3개" — 크기 3 최소 힙
k = 3  ,  힙은 항상 크기 3 이하로 유지해요 (루트 = 최솟값)
​
5 :  넣어요                     힙 {5}
1 :  넣어요                     힙 {1, 5}
8 :  넣어요                     힙 {1, 5, 8}
3 :  넣으면 크기 4  →  최소 1 버림  힙 {3, 5, 8}
9 :  넣으면 크기 4  →  최소 3 버림  힙 {5, 8, 9}
​
가장 큰 3개 → {5, 8, 9}  ,  루트 5 는 3번째로 큰 수예요
스트림 중앙값도 힙 두 개로 풀어요. 작은 절반은 최대 힙, 큰 절반은 최소 힙에 담고 두 힙 크기를 비슷하게 맞추면, 두 루트만 보고 언제든 중앙값을 바로 알 수 있어요.

패턴 코드

크기 K 최소 힙으로 가장 큰 K개 유지파이썬은 내장 heapq 를, JS는 직접 만든 최소 힙을 써요.
javascript
class MinHeap {
  constructor() { this.data = []; }
  get size() { return this.data.length; }
  peek() { return this.data[0]; }
  push(v) {
    this.data.push(v);
    let i = this.data.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.data[p] <= this.data[i]) break;
      [this.data[p], this.data[i]] = [this.data[i], this.data[p]];
      i = p;
    }
  }
  pop() {
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      let i = 0;
      const n = this.data.length;
      while (true) {
        let s = i;
        const l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && this.data[l] < this.data[s]) s = l;
        if (r < n && this.data[r] < this.data[s]) s = r;
        if (s === i) break;
        [this.data[s], this.data[i]] = [this.data[i], this.data[s]];
        i = s;
      }
    }
    return top;
  }
}
​
function kLargest(nums, k) {
  const heap = new MinHeap();
  for (const x of nums) {
    heap.push(x);
    if (heap.size > k) heap.pop(); // 가장 작은 걸 버려요
  }
  // heap.peek() 은 K번째로 큰 수예요
  return heap.data.slice().sort((a, b) => a - b);
}

이 유형으로 풀어보기

← 다음 큰 수 — 모노토닉 스택이분탐색 — 값·경계 찾기 →