🎲 백준 최소 힙 1927번 [JS]

🧶 1. 힙에 값 추가 : 배열의 마지막에 넣고 부모 인덱스랑 비교하며 자리를 찾는다. (bubbleUp)
2. 힙(MinHeap)에서 가장 작은 값 삭제 : 배열의 마지막 원소를 루트 자리에 넣고 왼쪽 자식과 오른쪽 자식과 비교하며 자리를 찾는다. (bubbleDown)
🧸 이제 힙을 스스로 구현할 수 있다!!

코드

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n").map(Number);
const N = input.shift();

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

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  add(value) {
    this.heap.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    let parentIndex = Math.floor((index - 1) / 2);

    while (
      this.heap[parentIndex] &&
      this.heap[parentIndex] > this.heap[index]
    ) {
      this.swap(parentIndex, index);
      index = parentIndex;
      parentIndex = Math.floor((index - 1) / 2);
    }
  }

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

    let root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();

    return root;
  }

  bubbleDown() {
    let index = 0;
    let leftChild = index * 2 + 1;
    let rightChild = index * 2 + 2;

    while (
      (this.heap[leftChild] && this.heap[leftChild] < this.heap[index]) ||
      (this.heap[rightChild] && this.heap[rightChild] < this.heap[index])
    ) {
      let min = leftChild;

      if (this.heap[rightChild] && this.heap[leftChild] > this.heap[rightChild])
        min = rightChild;

      this.swap(min, index);

      index = min;
      leftChild = index * 2 + 1;
      rightChild = index * 2 + 2;
    }
  }
}

const minHeap = new MinHeap();
let answer = "";

for (let i = 0; i < N; i++) {
  if (input[i] === 0) answer += minHeap.remove() + "\n";
  else minHeap.add(input[i]);
}

console.log(answer);