[코딩테스트]백준 - 최대 힙(11279)

문제

최대 힙(11279)

해결한 코드

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 maxHeap {
    constructor() {
        this.nodes = []
    }

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

    bubbleUp(index = this.nodes.length - 1) {
        if (index < 1) return
        let currentNode = this.nodes[index]
        let parentIndex = Math.floor((index - 1) / 2)
        let parentNode = this.nodes[parentIndex]

        if (parentNode >= currentNode) return

        this.nodes[parentIndex] = currentNode
        this.nodes[index] = parentNode
        index = parentIndex
        this.bubbleUp(index)
    }

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

    trickleDown(index = 0) {
        let leftChildIndex = index * 2 + 1
        let rightChildIndex = index * 2 + 2
        let length = this.nodes.length
        let maximum = index

        if (!this.nodes[leftChildIndex] && !this.nodes[rightChildIndex]) return

        if (!this.nodes[rightChildIndex]) {
            if (this.nodes[leftChildIndex] > this.nodes[maximum]) {
                maximum = leftChildIndex
            }
        }

        if (this.nodes[leftChildIndex] < this.nodes[rightChildIndex]) {
            if (rightChildIndex <= length && this.nodes[rightChildIndex] > this.nodes[maximum]) {
                maximum = rightChildIndex
            }
        } else {
            if (leftChildIndex <= length && this.nodes[leftChildIndex] > this.nodes[maximum]) {
                maximum = leftChildIndex
            }
        }

        if (maximum !== index) {
            let t = this.nodes[maximum]
            this.nodes[maximum] = this.nodes[index]
            this.nodes[index] = t
            this.trickleDown(maximum)
        }
    }
}
const heap = new maxHeap()
let extracts = ''
operations.forEach((operation, index) => {
    if (operation !== 0) {
        heap.insert(operation)
    } 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. 연산 숫자에 따라 값을 출력한다.