보통힙자료구조

최소 힙 직접 구현

연산 목록 operations가 주어져요. 최소 힙을 직접 만들어 순서대로 처리하고, 값을 꺼내는 연산의 결과만 모아 배열로 반환해요.

연산은 세 가지예요. ["push", x]는 x를 넣고 아무것도 반환하지 않아요. ["pop"]은 가장 작은 값을 꺼내 반환해요. ["peek"]은 가장 작은 값을 꺼내지 않고 확인만 해요. 힙이 비어 있으면 pop과 peek 모두 null을 반환해요.

결과 배열에는 pop과 peek의 반환값만 순서대로 담아요.

이 문제의 목적은 정렬 함수를 부르는 게 아니라 힙 내부 동작을 직접 만들어 보는 거예요. 배열을 완전 이진 트리로 보고, 인덱스 i의 부모가 (i-1)/2, 자식이 2i+1과 2i+2라는 규칙 위에서 위로 올리기(sift up)와 아래로 내리기(sift down)를 구현해 보세요.

Python에는 heapq가 내장되어 있지만, 이 문제만큼은 직접 만들어 보길 권해요. 다음 문제부터는 마음껏 써요.

예시

예시 1

입력: operations = [["push", 5], ["push", 3], ["push", 8], ["pop"], ["pop"], ["pop"]]
출력: [3, 5, 8]
설명: 넣은 순서와 무관하게 작은 값부터 나와요.

예시 2

입력: operations = [["push", 4], ["peek"], ["push", 2], ["peek"], ["pop"], ["peek"]]
출력: [4, 2, 2, 4]
설명: peek은 꺼내지 않으니까 두 번째와 세 번째 결과가 모두 2예요.

예시 3

입력: operations = [["push", 1], ["pop"], ["pop"]]
출력: [1, null]
설명: 두 번째 pop은 힙이 비어 있어 null이에요.

제한 사항

1 ≤ operations.length ≤ 100,000
-10^9 ≤ x ≤ 10^9
같은 값이 여러 번 들어올 수 있어요.

push는 배열 끝에 넣고 부모보다 작은 동안 부모와 맞바꾸며 올라가요. pop은 뿌리를 빼내고 마지막 원소를 뿌리에 올린 뒤, 두 자식 중 더 작은 쪽과 맞바꾸며 내려가요. 두 연산 모두 높이만큼만 움직이니까 O(log n)이에요.

javascript
Copy code
class MinHeap {
  /** @param {(a: any, b: any) => number} [compare] 음수면 a가 먼저 나옵니다. */
  constructor(compare) {
    this.items = [];
    this.compare = compare ?? ((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  }
  get size() {
    return this.items.length;
  }
  peek() {
    return this.items.length > 0 ? this.items[0] : null;
  }
  push(value) {
    const a = this.items;
    a.push(value);
    let i = a.length - 1;
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.compare(a[parent], a[i]) <= 0) break;
      [a[parent], a[i]] = [a[i], a[parent]];
      i = parent;
    }
  }
  pop() {
    const a = this.items;
    if (a.length === 0) return null;
    const top = a[0];
    const last = a.pop();
    if (a.length > 0) {
      a[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let small = i;
        if (l < a.length && this.compare(a[l], a[small]) < 0) small = l;
        if (r < a.length && this.compare(a[r], a[small]) < 0) small = r;
        if (small === i) break;
        [a[small], a[i]] = [a[i], a[small]];
        i = small;
      }
    }
    return top;
  }
}
function heapOps(operations) {
  const heap = new MinHeap();
  const out = [];
  for (const [kind, value] of operations) {
    if (kind === "push") heap.push(value);
    else if (kind === "pop") out.push(heap.pop());
    else out.push(heap.peek());
  }
  return out;
}

이전 문제N-Queen

다음 문제가장 많이 등장한 K개 원소

예시 테스트만 실행 (Cmd/Ctrl+Enter)

숨김 테스트까지 채점 (Cmd/Ctrl+Shift+Enter)

에디터를 불러오고 있어요…

코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.