[백준] 최대 힙 #11279

설명

C++의 priority_queue는 최대 힙이므로 그냥 STL을 사용해서 풀었다.
JS의 경우 Heap 자료구조가 없어서 직접 구현했는데 실수를 좀 해서 다른 사람의 풀이를 참고했다.

Node.js 풀이

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const N = Number(input[0]);
const commands = input.slice(1, 1 + N).map(Number);

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  empty() {
    return this.heap.length === 0 ? true : false;
  }
  insert(value) {
    this.heap.push(value);
    this.bubbleUp();
  }
  bubbleUp() {
    let currentIndex = this.heap.length - 1;
    while (currentIndex > 0) {
      const parentIndex = Math.floor((currentIndex - 1) / 2);
      if (this.heap[parentIndex] >= this.heap[currentIndex]) break;
      [this.heap[currentIndex], this.heap[parentIndex]] = [
        this.heap[parentIndex],
        this.heap[currentIndex],
      ];
      currentIndex = parentIndex;
    }
  }
  pop() {
    if (this.heap.length === 1) return this.heap.pop();
    const max = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown(0);
    return max;
  }
  bubbleDown(index) {
    const leftNodeIndex = 2 * index + 1;
    const rightNodeIndex = 2 * index + 2;
    const length = this.heap.length;
    let maxIndex = index;
    if (
      leftNodeIndex < length &&
      this.heap[leftNodeIndex] > this.heap[maxIndex]
    ) {
      maxIndex = leftNodeIndex;
    }
    if (
      rightNodeIndex < length &&
      this.heap[rightNodeIndex] > this.heap[maxIndex]
    ) {
      maxIndex = rightNodeIndex;
    }
    if (maxIndex !== index) {
      [this.heap[index], this.heap[maxIndex]] = [
        this.heap[maxIndex],
        this.heap[index],
      ];
      this.bubbleDown(maxIndex);
    }
  }
}

const solution = (N, commands) => {
  const maxHeap = new MaxHeap();
  let answer = '';
  commands.forEach((command) => {
    if (command === 0) {
      if (maxHeap.empty()) answer += '0\n';
      else answer += maxHeap.pop() + '\n';
    } else {
      maxHeap.insert(command);
    }
  });
  return answer;
};

console.log(solution(N, commands));

C++ 풀이

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N; cin >> N;
    priority_queue<int> PQ;
    cout << "-----------------" << '\n';
    for (int i=0; i<N; i++) {
        int cmd; cin >> cmd;
        if (cmd == 0) {
            if (PQ.empty()) {
                cout << '0' << '\n';
                continue;
            } 
            cout << PQ.top() << '\n';
            PQ.pop();
        }
        else {
            PQ.push(cmd);
        }
    }
    return 0;
}