힙(heap)은 우선순위 큐(priority queue)를 구현하는 데 사용되는 트리 기반의 자료구조입니다. 힙은 각 노드의 값이 해당 노드의 자식 노드의 값보다 작거나 같은 최대 힙(max heap)과 크거나 같은 최소 힙(min heap)으로 구분됩니다. 이번 포스트에서는 코틀린의 집합(Set)을 사용하여 간단한 최소 힙(min heap)을 구현하는 방법을 살펴보겠습니다.

집합(Set)을 이용한 최소 힙 구현

코틀린의 Set은 중복을 허용하지 않는 값들의 모임입니다. 이 특성을 이용하여 최소 힙을 구현할 수 있습니다. 각 원소를 추가하는 동작 시, 이미 힙에 존재하는지 검사한 뒤 없다면 추가하는 방식으로 최소 힙을 유지할 수 있습니다.

class MinHeap<T : Comparable<T>> {
    private val elements: MutableSet<T> = TreeSet()

    fun add(value: T) {
        if (!elements.contains(value)) {
            elements.add(value)
        }
    }

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

    fun poll(): T? {
        val element = peek()
        if (element != null) {
            elements.remove(element)
        }
        return element
    }
}

위 코드에서 MinHeap 클래스는 Comparator를 이용한 TreeSet을 내부적으로 사용합니다. add 함수는 새로운 요소를 추가할 때 중복을 허용하지 않도록 Set의 특성을 이용합니다. peek 함수는 힙의 최소값을 반환하고, poll 함수는 최소값을 반환한 뒤 제거합니다.

사용 예시

fun main() {
    val minHeap = MinHeap<Int>()
    minHeap.add(5)
    minHeap.add(8)
    minHeap.add(2)
    minHeap.add(7)

    println(minHeap.poll()) // 2
    println(minHeap.poll()) // 5
    println(minHeap.poll()) // 7
}

위 예시에서는 MinHeap을 사용하여 정수를 추가하고, poll 함수를 사용하여 최소값을 순서대로 출력하고 제거하는 예시를 보여줍니다.

결론

코틀린의 집합(Set)을 이용하여 최소 힙을 간단히 구현하는 방법에 대해 살펴보았습니다. 이를 통해 우선순위 큐와 같은 힙 자료구조를 쉽게 활용할 수 있습니다. 추가로, 힙을 좀 더 복잡하게 구현하고 싶다면 자체적인 힙 자료구조 클래스를 구축하여 사용해 볼 수도 있습니다.

참고 자료:

• Kotlin - Sets
• The heap data structure