[Kotlin] Kotlin PriorityQueue 클래스 사용해 우선순위큐 사용하기

이번 글에서 다룰 내용

이전 글에서 Priority Queue가 무엇인지, 내부가 어떻게 이루어져 있는지, 시간 복잡도는 어떻게 되는지 다루었다. 이번 글에서는 Kotlin에서 실제로 Priority Queue를 어떻게 선언하고 사용할 수 있는지 다루고자 한다.

 

PriorityQueue 클래스 사용해 PriorityQueue 초기화하기

Kotlin에서 Priority Queue를 사용하기 위해서는 java.util 패키지의 PriorityQueue 클래스를 사용하면 된다. PriorityQueue 클래스는 다음과 같이 초기화할 수 있다.

val priorityQueue = PriorityQueue<Int>()

 

PriorityQueue에 값 삽입 하기

PriorityQueue에 값을 추가하기 위해서는 offer 함수를 사용하면 된다.

 

Kotlin, Java의 PriorityQueue는 Min-Heap 방식으로 구현되어, 우선순위가 낮은 것이 Queue의 앞쪽에 온다. 따라서, 11, 14, 13, 12, 15를 순서대로 입력했을 때 PriorityQueue 내부는 다음과 같이 변화한다.

val priorityQueue = PriorityQueue<Int>()
priorityQueue.offer(11) // [11]
priorityQueue.offer(14) // [11, 14]
priorityQueue.offer(13) // [11, 13, 14]
priorityQueue.offer(12) // [11, 12, 13, 14]
priorityQueue.offer(15) // [11, 12, 13, 14, 15]

 

PriorityQueue에서 값 빼내기

PriorityQueue에서 값을 빼내기 위해서는 poll 함수를 사용하면 된다.

 

while문을 사용해 빼낸 값들을 출력하면 11, 12, 13, 14, 15가 출력되는 것을 확인할 수 있다.

while(priorityQueue.isNotEmpty()) {
    println(priorityQueue.poll())
}
// 11
// 12
// 13
// 14
// 15

 

PriorityQueue 내부의 원소 개수 구하기

PriorityQueue는 내부에 size를 가지고 있어서 size 프로퍼티를 사용해 내부의 원소 개수를 바로 알 수 있다.

val priorityQueue = PriorityQueue<Int>()
priorityQueue.offer(11)
priorityQueue.offer(14)
priorityQueue.offer(13)
priorityQueue.offer(12)
priorityQueue.offer(15)

println(priorityQueue.size) // 5

 

 

Comparable 인터페이스 구현하는 클래스 만들어서 PriorityQueue의 우선 순위 변경하기

Comparable 인터페이스를 구현하는 클래스를 만들면 PriorityQueue의 우선 순위를 변경할 수 있다.  PriorityQueue는 min-heap방식으로 만들어져 있어서 우선순위가 낮은 것이 맨 앞에 온다는 점을 명심하자.

 

코틀린의 기본 Int는 값이 낮을 수록 우선순위가 낮지만, ComparableInt를 아래와 같이 구현하면 값이 높을수록 우선순위가 낮도록 만들 수 있다.

data class ComparableInt(val int: Int) : Comparable<ComparableInt> {
    override fun compareTo(other: ComparableInt): Int {
        return other.int - int // 마이너스이면 other의 우선순위가 높은 것 플러스이면 this의 우선순위가 높은 것
    }
}

 

 

따라서 위의 ComparableInt를 인자로 받는 PriorityQueue를 만들어 원소들을 넣으면 기존과 완전히 반대로 동작해 값이 높은 것이 앞으로 오는 것을 볼 수 있다.

val priorityQueue = PriorityQueue<ComparableInt>()
priorityQueue.offer(ComparableInt(11)) // [11]
priorityQueue.offer(ComparableInt(14)) // [14, 11]
priorityQueue.offer(ComparableInt(13)) // [14, 13, 11]
priorityQueue.offer(ComparableInt(12)) // [14, 13, 12, 11]
priorityQueue.offer(ComparableInt(15)) // [15, 14, 13, 12, 11]