1927번 (최소 힙)

const fs = require('fs');
const input = fs.readFileSync('./dev/stdin.txt').toString().trim().split('\n').map(Number);
const N = input.shift();
class MinHeap {
constructor() {
this.heap = [];
}
getLastIdx() {
return this.heap.length - 1;
}
insert(data) {
this.heap.push(data);
let curIdx = this.getLastIdx();
const curData = this.heap[curIdx];
while (curIdx > 0) {
// 부모 노드의 인덱스와 값 할당
const parentIdx = Math.floor((curIdx - 1) / 2);
const parentData = this.heap[parentIdx];
// 현재 데이터가 부모 데이터보다 크거나 같을 경우 느슨한 정렬이 된 상태이므로 break
if (curData >= parentData) break;
this.heap[curIdx] = parentData;
curIdx = parentIdx;
}
this.heap[curIdx] = curData;
}
delete() {
if (this.heap.length === 0) {
return 0;
} else if (this.heap.length === 1) {
return this.heap.pop();
} else {
const data = this.heap[0];
this.heap[0] = this.heap[this.getLastIdx()];
this.heap.pop();
let curIdx = 0;
const curData = this.heap[0];
while (curIdx <= this.getLastIdx()) {
const leftChildIdx = curIdx * 2 + 1;
const rightChildIdx = curIdx * 2 + 2;
// 자신이 리프 노드일 경우
if (leftChildIdx > this.getLastIdx()) break;
const leftChildData = this.heap[leftChildIdx];
const rightChildData = this.heap[rightChildIdx];
const childIdx = rightChildData !== undefined && rightChildData < leftChildData ? rightChildIdx : leftChildIdx;
const childData = this.heap[childIdx];
// 느슨한 정렬이 된 상태
if (curData <= childData) break;
this.heap[curIdx] = childData;
curIdx = childIdx;
}
this.heap[curIdx] = curData;
return data;
}
}
}
const minHeap = new MinHeap();
const answer = [];
for (let i = 0; i < N; i++) {
if (input[i] > 0) {
minHeap.insert(input[i]);
} else {
answer.push(minHeap.delete());
}
}
console.log(answer.join('\n'));
  • insert 메소드와 delete 메소드는 각각 삽입, 삭제 후 느슨한 정렬상태가 되도록 한다.
  • input이 0보다 크면 insert를 하고, 그게 아니면 delete가 리턴한 값을 정답 배열에 push한다.
  • input이 0이고 heap에 아무것도 없을 경우 delete 메소드는 0을 리턴한다.