최소 힙

최소 힙

문제 설명

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.

배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

예제 입력

9
0
12345678
1
2
0
0
0
0
32

예제 출력

0
1
2
12345678
0

---

문제 풀이

const fs = require("fs");
const path = require("path");
const input = fs
  .readFileSync(
    process.platform === "linux"
      ? "dev/stdin"
      : path.join(__dirname, "input.txt")
  )
  .toString()
  .trim()
  .split("\n");

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(num) {
    let heap = this.heap;
    heap.push(num);

    if (heap.length > 0) {
      let childIdx = heap.length - 1;
      let parentIdx = Math.floor((childIdx - 1) / 2);

      while (childIdx !== 0 && heap[parentIdx] > heap[childIdx]) {
        let [child, parent] = [heap[childIdx], heap[parentIdx]];

        heap[childIdx] = parent;
        heap[parentIdx] = child;

        childIdx = parentIdx;
        parentIdx = Math.floor((childIdx - 1) / 2);
      }
    }
  }

  popMin() {
    let heap = this.heap;

    if (heap.length === 0) return 0;
    if (heap.length === 1) return heap.pop();

    let min = heap[0];
    heap[0] = heap.pop();

    let parentIdx = 0;
    let leftChildIdx = parentIdx * 2 + 1;
    let rightChildIdx = parentIdx * 2 + 2;

    while (
      (heap[leftChildIdx] && heap[leftChildIdx] < heap[parentIdx]) ||
      (heap[rightChildIdx] && heap[rightChildIdx] < heap[parentIdx])
    ) {
      let parent = heap[parentIdx];
      let childIdx = leftChildIdx;

      if (heap[rightChildIdx] && heap[rightChildIdx] < heap[leftChildIdx]) {
        childIdx = rightChildIdx;
      }

      let child = heap[childIdx];

      heap[parentIdx] = child;
      heap[childIdx] = parent;

      parentIdx = childIdx;
      leftChildIdx = parentIdx * 2 + 1;
      rightChildIdx = parentIdx * 2 + 2;
    }
    return min;
  }
}

const solution = (input) => {
  let idx = 0;
  const minHeap = new MinHeap();
  const N = Number(input[idx++]);
  let result = "";
  for (let i = 0; i < N; i++) {
    let el = Number(input[idx++]);

    if (el == 0) result += minHeap.popMin() + "\n";
    else minHeap.push(el);
  }
  console.log(result);
};

solution(input);

아이디어 / 접근법

1. 최소 힙
2. 0들어오면 pop
3. 아니라면 push

후기

이 문제 또한 JS 가 아니었다면 쉽게 풀렸을 문제였으나.. JS 이기 때문에 직접 다 구현을 해줘야 했다 그래서 저번에 풀었던 최대 힙에서 조건만 바꿔서 돌렸더니 성공!