[PS]우선순위 큐(Periorty Queue)와 힙(Heapq)

Hood·2025년 1월 22일

heapq periorty queue ps

PS

목록 보기

13/15

✍ Kotlin을 사용한 PS 문제 풀이를 위한 알고리즘

소속 중인 A&I 동아리에서 코딩 역량을 강화하고자
코딩캠프를 진행하며 작성한 포스트입니다.
해당 포스트는 Kotlin을 기반으로 작성하였습니다.

들어가기 전

우선순위 큐는 무엇인가?

큐(Queue)는 FIFO(First In First Out) 특징을 가지는 선형 자료구조입니다.
즉, 먼저 들어온 원소가 먼저 나가는 구조입니다.

하지만 알고리즘 문제를 풀다 보면 단순히 먼저 들어온 순서대로 처리하는 것이 아니라,
어떤 기준에 따라 우선순위가 높은 원소를 먼저 꺼내야 하는 경우가 있습니다.

이처럼 우선순위가 높은 원소를 먼저 반환하는 자료구조를
우선순위 큐(Priority Queue)라고 합니다.

여기서 주의할 점은, 우선순위 큐는 일반적인 큐처럼 생겼지만
반드시 FIFO 순서만 따르는 것은 아니라는 점입니다.
핵심은 삽입 순서가 아니라 우선순위 기준으로 원소를 꺼낸다는 것입니다.

만약 배열에서 매번 우선순위가 가장 높은 원소를 직접 찾아 꺼낸다면,
한 번 꺼낼 때마다 선형 탐색이 필요하므로 O(N)이 걸립니다.
이 과정을 여러 번 반복하면 전체 시간 복잡도는 O(N^2)까지 커질 수 있습니다.

그래서 우선순위 큐는 보통 힙(Heap) 자료구조를 이용해 구현합니다.

힙(Heap)

힙은 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 나뉘며,
완전 이진 트리 형태를 가지는 자료구조입니다.

다만 힙은 배열 전체가 완전히 정렬되어 있는 구조는 아닙니다.
힙에서 중요한 것은 부모와 자식 사이의 우선순위 관계입니다.

최소 힙: 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
최대 힙: 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.

즉, 최소 힙에서는 항상 루트 노드가 가장 작은 값을 가지며,
최대 힙에서는 항상 루트 노드가 가장 큰 값을 가집니다.

최소 힙(Min Heap)

최소 힙은 완전 이진 트리 구조를 유지하면서,
각 부모 노드가 자식 노드보다 작거나 같은 값을 가지도록 구성된 자료구조입니다.

초기 최소 힙 자료구조가 아래와 같은 트리 구조를 이룬다고 가정해 보겠습니다.

여기에 새로운 원소 5가 삽입된다고 해보겠습니다.
새로운 원소는 먼저 트리의 가장 마지막 위치에 들어갑니다.

하지만 이 상태에서는 최소 힙 조건을 만족하지 못합니다.
왜냐하면 5가 부모 노드인 7보다 작기 때문입니다.

이 문제를 해결하려면 새로 삽입된 원소를 부모와 비교하면서
올바른 위치로 올려 보내야 합니다.
이 과정을 siftUp이라고 합니다.

정리하면 다음과 같습니다.

새 원소의 부모 인덱스를 찾습니다.
부모보다 더 작은 값이라면 서로 위치를 바꿉니다.
이 과정을 루트에 도달하거나 조건을 만족할 때까지 반복합니다.

따라서 5와 7의 위치를 바꾸게 됩니다.

원소 추출

최소 힙에서 원소를 추출하면 항상 루트 노드의 값이 반환됩니다.

다만 루트 노드를 제거한 뒤에도 힙의 규칙은 계속 유지되어야 합니다.
그래서 보통 다음과 같은 과정을 거칩니다.

루트 노드와 마지막 노드를 교환합니다.
마지막 노드를 제거합니다.
새 루트 노드를 아래로 내려 보내며 힙 속성을 복구합니다.

이처럼 루트에서 시작해 아래로 내려가며 재정렬하는 과정을
siftDown이라고 합니다.

배열로 표현하는 최소 힙

힙은 트리처럼 보이지만, 실제 구현에서는 보통 배열로 표현합니다.

예를 들어 아래와 같은 힙 구조가 있다고 생각해 보겠습니다.

배열의 인덱스는 0부터 시작하고,
트리의 각 노드는 위에서 아래로, 왼쪽에서 오른쪽 순서대로 저장됩니다.

이때 완전 이진 트리의 성질을 이용하면
부모와 자식의 인덱스를 다음과 같이 계산할 수 있습니다.

부모 노드 인덱스: (child - 1) / 2
왼쪽 자식 노드 인덱스: parent * 2 + 1
오른쪽 자식 노드 인덱스: parent * 2 + 2

이 공식을 알고 있으면,
트리를 따로 만들지 않고도 배열만으로 힙을 구현할 수 있습니다.

노드 삽입(Enqueue)

이제 노드 2를 삽입한다고 가정해 보겠습니다.
새로운 노드는 항상 힙의 가장 마지막 인덱스에 들어갑니다.

삽입 직후에는 힙 조건이 깨질 수 있으므로,
새로 추가된 노드를 부모와 비교하여 더 작다면 서로 위치를 바꿉니다.
이 과정을 siftUp이라고 하며, 루트에 도달하거나 조건을 만족할 때까지 반복합니다.

2는 5보다 작기 때문에 자리를 교체합니다.

이후에도 부모와 비교했을 때 여전히 더 작다면 다시 교환합니다.

이렇게 해서 삽입 연산이 끝나면 힙 속성이 다시 유지됩니다.

노드 추출(Dequeue)

이번에는 루트 노드를 제거한다고 생각해 보겠습니다.

루트 노드를 바로 삭제하면 배열 중간이 비게 되므로,
먼저 루트와 마지막 노드를 교환합니다.

그 이유는 배열의 마지막 원소를 제거하는 연산이 O(1)이기 때문입니다.

그다음 마지막 노드를 제거합니다.

이제 루트 노드부터 시작해 자식 노드와 비교하며
더 작은 값을 가진 자식과 위치를 바꾸어야 합니다.
이 과정을 siftDown이라고 합니다.

스왑이 일어난 뒤에는 바뀐 위치에서 다시 자식 노드를 확인합니다.

3이 더 우선순위가 높기 때문에 다시 교환합니다.

리프 노드에 도달하거나 더 이상 교환할 필요가 없으면 종료합니다.

In Kotlin

이제 enqueue, dequeue, siftUp, siftDown을 이용해
우선순위 큐를 직접 구현해 보겠습니다.

이번 구현에서는 일반적인 우선순위 큐 방식에 맞게
dequeue()가 특정 원소를 찾는 것이 아니라 루트 원소를 꺼내는 형태로 구성하였습니다.

class Heapq<T : Comparable<T>>(
    private val isMinHeap: Boolean = true
) {
    private val data = mutableListOf<T>()

    private fun hasHigherPriority(a: T, b: T): Boolean {
        return if (isMinHeap) a < b else a > b
    }

    val size: Int
        get() = data.size

    fun peek(): T? = data.firstOrNull()

    fun enqueue(element: T) {
        data.add(element)
        siftUp(data.lastIndex)
    }

    fun dequeue(): T? {
        if (data.isEmpty()) return null
        if (data.size == 1) return data.removeAt(0)

        val root = data[0]
        data[0] = data.removeAt(data.lastIndex)
        siftDown(0)
        return root
    }

    private fun siftUp(startIndex: Int) {
        var child = startIndex

        while (child > 0) {
            val parent = (child - 1) / 2
            if (!hasHigherPriority(data[child], data[parent])) break

            data.swap(child, parent)
            child = parent
        }
    }

    private fun siftDown(startIndex: Int) {
        var parent = startIndex

        while (true) {
            val leftChild = parent * 2 + 1
            val rightChild = parent * 2 + 2
            var candidate = parent

            if (leftChild < data.size &&
                hasHigherPriority(data[leftChild], data[candidate])) {
                candidate = leftChild
            }

            if (rightChild < data.size &&
                hasHigherPriority(data[rightChild], data[candidate])) {
                candidate = rightChild
            }

            if (candidate == parent) break

            data.swap(parent, candidate)
            parent = candidate
        }
    }

    private fun MutableList<T>.swap(i: Int, j: Int) {
        val temp = this[i]
        this[i] = this[j]
        this[j] = temp
    }

    override fun toString(): String = data.toString()
}

fun main() {
    val minHeap = Heapq<Long>(isMinHeap = true)

    minHeap.enqueue(1)
    minHeap.enqueue(3)
    minHeap.enqueue(4)
    minHeap.enqueue(5)
    minHeap.enqueue(6)
    minHeap.enqueue(7)
    minHeap.enqueue(8)
    minHeap.enqueue(2)

    println(minHeap.peek())    // 1
    println(minHeap.size)      // 8
    println(minHeap)           // 내부 배열 상태
    println(minHeap.dequeue()) // 1 추출
    println(minHeap)
}