[코딩테스트]백준 - 최소 힙(1927)

문제

최소 힙(1927)

해결한 코드

let fs = require('fs');
var input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
// let input = fs.readFileSync(__dirname + '/stdin.txt').toString().replace(/\r/g, "").trim().split('\n');
let n = +input[0]
let operations = []
for (let i = 1; i < input.length; i++) {
    operations.push(+input[i])
}

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

    insert(data) {
        this.nodes.push(data)
        this.bubbleUp()
    }

    bubbleUp(index = this.nodes.length - 1) {
        if (index < 1) return
        const currentNode = this.nodes[index]
        const parentIndex = Math.floor((index - 1) / 2)
        const parentNode = this.nodes[parentIndex]
        // 부모값이 더 작으면 끝내기 
        if (parentNode <= currentNode) return
        // 그렇지 않으면 자리바꾸기
        this.nodes[index] = parentNode
        this.nodes[parentIndex] = currentNode
        index = parentIndex
        this.bubbleUp(index)
    }

    extract() {
        const min = this.nodes[0]
        if (this.nodes.length === 1) {
            this.nodes.pop()
            return min
        }
        this.nodes[0] = this.nodes.pop()
        this.trickleDown()
        return min
    }

    trickleDown(index = 0) {
        const leftChildIndex = index * 2 + 1
        const rightChildIndex = index * 2 + 2
        const length = this.nodes.length
        let minimum = index
        if (!this.nodes[leftChildIndex] && !this.nodes[rightChildIndex]) return;
        if (!this.nodes[rightChildIndex]) {
            if (this.nodes[leftChildIndex] < this.nodes[minimum]) {
                minimum = leftChildIndex
            }
        }
        if (this.nodes[leftChildIndex] > this.nodes[rightChildIndex]) {
            if (rightChildIndex <= length && this.nodes[rightChildIndex] < this.nodes[minimum]) {
                minimum = rightChildIndex
            }
        } else {
            if (leftChildIndex <= length && this.nodes[leftChildIndex] < this.nodes[minimum]) {
                minimum = leftChildIndex
            }
        }
        if (minimum !== index) {
            let t = this.nodes[minimum]
            this.nodes[minimum] = this.nodes[index]
            this.nodes[index] = t
            this.trickleDown(minimum)
        }
    }
}
const heap = new MinHeap()
let extracts = ''
operations.forEach((e, index) => {
    if (e !== 0) {
        heap.insert(e)
    } else {
        if (heap.nodes.length === 0) {
            extracts += '0' + '\n'
        } else {
            let t = heap.extract()
            extracts += t + '\n'
        }
    }
})

console.log(extracts.trim())

풀이

※ 자료구조 힙을 이해한다.

1. 힙을 구현한다.

1-1. 힙의 삽입

• 현재 힙이 비어있으면 : 그냥 push한다.
• 비어있지 않으면 : 일단 push하고, push된 가장 마지막 원소를 부모노드와 비교해간다.
  • 부모노드의 index: (현재 노드의 index - 1) / 2
  • 부모노드보다 값이 크면? 문제 ㄴㄴ
  • 값이 작으면? 부모-자식 관계가 바뀌어야 하므로, 서로 swap한다.

제자리를 찾을 때까지 재귀적으로 계산한다.

1-2. 힙의 삭제

• 현재 힙이 비어있으면 : 그냥 0만 출력한다.
• 비어있지 않으면 :
  • 힙의 길이가 1이면 : pop하고 해당 원소를 return한다.
  • 1보다 더 크면 : 루트 노드를 먼저 꺼내고, 현재 힙에 있는 가장 마지막 노드를 루트 자리에 놓는다.
  • 그리고 부모-자식 관계를 재정리한다.
    • 왼쪽 자식 index: (현재 노드의 index × 2) + 1
    • 오른쪽 자식 index: (현재 노드의 index × 2) + 2

자식 노드보다 값이 작으면? 문제 ㄴㄴ
값이 크면? 부모-자식 관계가 바뀌어야 한다.

📌 고려해야 할 조건

• 왼쪽 자식만 있으면?
  왼쪽 자식과 비교한다.
• 자식이 둘 다 있으면?
  두 자식 중 값이 더 작은 자식과 비교한다.
• 자식이 둘 다 없으면?
  마침내 제자리를 찾았다는 의미다. 재귀를 멈춘다.

2. 연산 숫자에 따라 값을 출력한다.