[백준][JS] 1927번 - 최소 힙

문제 유형

- 자료구조

- 우선순위 큐

 

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 

1. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 

2. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 

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

 

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

 

예제 입력

9
0
12345678
1
2
0
0
0
0
32

 

예제 출력

0
1
2
12345678
0

 

풀이

const [N, ...ARR] = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
  .toString()
  .trim()
  .split('\n')
  .map(Number);

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

  heapifyUp(index) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (parentIndex >= 0 && this.heap[index] < this.heap[parentIndex]) {
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      this.heapifyUp(parentIndex);
    }
  }

  heapifyDown(index) {
    const len = this.heap.length;
    let smallest = index;
    const leftChild = 2 * index + 1;
    const rightChild = 2 * index + 2;

    if (leftChild < len && this.heap[leftChild] < this.heap[smallest]) {
      smallest = leftChild;
    }

    if (rightChild < len && this.heap[rightChild] < this.heap[smallest]) {
      smallest = rightChild;
    }

    if (smallest !== index) {
      [this.heap[smallest], this.heap[index]] = [this.heap[index], this.heap[smallest]];
      this.heapifyDown(smallest);
    }
  }

  insert(value) {
    this.heap.push(value);
    this.heapifyUp(this.heap.length - 1);
  }

  extractMin() {
    if (this.heap.length === 0) {
      return null;
    }
    
    const min = this.heap[0];
    const lastIdx = this.heap.length - 1;
    this.heap[0] = this.heap[lastIdx];
    this.heap.pop();
    this.heapifyDown(0);

    return min;
  }
}


const minHeap = new MinHeap();
const answer = [];

for (let i = 0; i < N; i++) {
  const x = ARR[i];

  if (x !== 0) {
    minHeap.insert(x);
  } else {
    const min = minHeap.extractMin() || 0;
    answer.push(min);
  }
}

console.log(answer.join('\n'));

최소 힙을 먼저 구현해야 한다.

 

최소 힙은 위에 부모 노드가 가장 작은 값이어야 한다. 

보통 트리는 배열 형태로 나타낸다. 

 

1. 새로운 값이 들어오면 배열의 가장 마지막에 추가를 하고 heapifyUp 메서드를 통해서 비교 자리를 찾는다.

2. 문제에서 가장 작은 값을 추출하고 배열에서 제거를 하라고 했으니 가장 작은 값을 extractMin 메서드를 통해 추출한 후

가장 밑에 있는 노드를 가지고 비교해 자리를 잡는 작업을 진행한다. 

3. heapifyDown 메서드를 호출해 자식 노드와 비교 해서 자리를 잡는다.