[백준] 최대 힙 ( 1279번)_JS

문제

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

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

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

 

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

 

출력

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

 

내 답안:
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\\n").map(Number) ;
let n = +input.shift() ;

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

  getParentIndex(i){
    return Math.floor((i-1)/2) ;
  }

  getChildLeftIndex(i){
    return i * 2 + 1 ;
  }

  getChildRightIndex(i){
    return i * 2 + 2 ;
  }

  swap(a,b){  //a,b = index
    let val = this.heap[a] ; 
    this.heap[a] = this.heap[b] ;
    this.heap[b] = val ;
  }

  push(data){
    this.heap.push(data) ;
    let nowIndex = this.heap.length-1 ;
    let parIndex = this.getParentIndex(nowIndex) ;

    while ((nowIndex > 0 )&&(this.heap[parIndex] < this.heap[nowIndex])){
      this.swap(parIndex, nowIndex) ;
      nowIndex = parIndex ;
      parIndex = this.getParentIndex(nowIndex) ;
    }
  }

  shift(){

    if (this.heap.length == 0 ) return 0 ;
    let result = this.heap[0] ;
    this.heap[0] = this.heap[this.heap.length -1 ] ;
    this.heap.pop() ;
    let nowIndex = 0 ;

    while(this.heap[this.getChildLeftIndex(nowIndex)] != undefined){
      let maxChildIndex = this.getChildLeftIndex(nowIndex) ;

      if (this.heap[this.getChildRightIndex(nowIndex)] > this.heap[maxChildIndex] ){
        maxChildIndex = this.getChildRightIndex(nowIndex) ; 
      }

      if (this.heap[nowIndex] < this.heap[maxChildIndex]) this.swap(nowIndex, maxChildIndex) ;
      nowIndex = maxChildIndex ;
    }

    return result ;
  }

}

let answer = "" ;
let heap = new Heap() ;
input.forEach( x => {
  if ( x == 0 ) answer += `${heap.shift()}\\n` ;
  else heap.push(x) ;
})
console.log(answer.trim()) ;