우선순위 큐(priority queue)는 데이터 구조 중 하나로, 항목을 삽입하거나 최댓값 또는 최솟값을 제거하는 연산을 지원합니다. 이중 우선순위 큐는 최댓값과 최솟값을 모두 제거할 수 있는 자료 구조입니다. 적은 양의 코드로 코틀린으로 이중 우선순위 큐를 쉽게 구현할 수 있습니다.

이중 우선순위 큐 알고리즘

이중 우선순위 큐는 내부적으로 최솟값과 최댓값을 저장하는 두 개의 우선순위 큐로 구성됩니다. 항목을 삽입하고 제거할 때는 두 우선순위 큐를 동기화하여 작업합니다.

import java.util.*

class DualPriorityQueue {
    private val minHeap = PriorityQueue<Int>()
    private val maxHeap = PriorityQueue<Int>(Comparator.reverseOrder())

    fun insert(value: Int) {
        minHeap.offer(value)
        maxHeap.offer(value)
    }

    fun removeMin() {
        maxHeap.remove(minHeap.poll())
    }

    fun removeMax() {
        minHeap.remove(maxHeap.poll())
    }

    fun isEmpty(): Boolean {
        return minHeap.isEmpty() && maxHeap.isEmpty()
    }
}

위 코드에서는 PriorityQueue를 이용하여 우선순위 큐를 사용하였는데, Offer를 통해 값 삽입, Poll을 통해 최솟값 또는 최댓값 제거를 수행합니다. 최댓값과 최솟값을 저장하는 두 개의 우선순위 큐를 동기화하여 이중 우선순위 큐를 구현했습니다.

결론

코틀린을 사용하여 이중 우선순위 큐를 간단하게 구현하는 방법을 살펴보았습니다. 이중 우선순위 큐는 두 가지 연산을 지원하여 데이터를 효율적으로 관리할 수 있는 자료 구조이며, 위에서 제시한 알고리즘을 활용하여 여러 다양한 문제에 적용할 수 있습니다.

참조: Kotlin PriorityQueue