[Chapter16] - 힙으로 우선순위 유지하기

[wolfy916]

힙

• 우선순위 큐를 구현하기 위해 자주 사용하는 자료구조
• 이진힙(최소/최대힙)
• Min-Max 힙 = 양 끝값 동시 접근
• Interval 힙 = 범위/중간 값 계산
• Comparator를 사용한 사용자 정의 힙
• ...

힙의 조건

1. 모든 노드가 힙 조건(Heap Condition) 을 만족해야 한다.
2. 트리가 완전(Complete) 해야한다.

힙 조건

• 부모 노드와 자식 노드의 관계를 정의하는 규칙
• 예시 - 숫자형 데이터의 최소/최대, 특수한 도메인 규칙, ...

완전 트리

• 트리의 마지막 레벨이 왼쪽부터 채워져 있어야 한다.
• 마지막 레벨을 제외한 모든 레벨은 꽉 채워져 있어야 한다.

간단한 최대힙 문제 풀이

• 문제 링크 : 11279번: 최대 힙

MaxHeap을 직접 구현한 코드

class MaxHeap {
    private val heap = mutableListOf<Int>()
    val size get() = heap.size
    val maxValue get() = heap.first()

    private fun getLeftChd(par: Int) = par * 2 + 1
    private fun getPar(chd: Int) = (chd - 1) / 2

    private fun swap(a: Int, b: Int) {
        val temp = heap[a]
        heap[a] = heap[b]
        heap[b] = temp
    }

    private fun siftDown() {
        var cur = 0; var chd = 1 // siftDown이 실행되는 시점에 heap.size는 2이상임
        while (chd < size) {
            val rightChd = chd + 1
            if (rightChd < size && heap[chd] < heap[rightChd]) {
                chd = rightChd
            }
            if (heap[cur] < heap[chd]) {
                swap(cur, chd)
                cur = chd
                chd = getLeftChd(cur)
            } else break
        }
    }

    private fun siftUp() {
        var cur = size - 1
        while (0 < cur) {
            val par = getPar(cur)
            if (heap[par] < heap[cur]) {
                swap(cur, par)
                cur = par
            } else break
        }
    }

    fun add(x: Int) {
        heap.add(x)
        siftUp()
    }

    fun poll(): Int {
        if (heap.isEmpty()) return 0 // 문제 출력 조건
        if (size == 1) return heap.removeLast()

        val data = heap.first()
        heap[0] = heap.removeLast()

        siftDown()

        return data
    }
}

fun solution(nums: List<Int>): String {
    val priorityQueue = MaxHeap()
    val outputList = mutableListOf<Int>()

    nums.forEach {
        if (it > 0) priorityQueue.add(it)
        else outputList.add(priorityQueue.poll())
    }

    return outputList.joinToString("\n")
}

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val nums = List(n) { readLine().toInt() }
    println(solution(nums))
}

PriorityQueue를 사용한 코드

fun solution(nums: List<Int>): String {
    val priorityQueue = PriorityQueue<Int>(compareByDescending { it })
    val outputList = mutableListOf<Int>()

    nums.forEach {
        if (it > 0) priorityQueue.add(it)
        else outputList.add(priorityQueue.poll() ?: 0)
    }

    return outputList.joinToString("\n")
}

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val nums = List(n) { readLine().toInt() }
    println(solution(nums))
}

결과

• 최대 데이터 개수 100,000 개

메모리 (KB)	시간 (ms)
35504	384
45840	408

1. Priority Queue 코드
2. MaxHeap 구현 코드