우선순위 큐

우선순위 큐(Priority Queue)

이진트리의 형태

오름차순 혹은 내림차순으로 값을 저장

 → 기본은 최소 힙 방식이기 때문에 오름차순

트리의 Top을 읽어 최대값이나 최소값을 가질 수 있음

→ 들어간 순서와 상관없이 오름차순인 경우에는 최소값, 내림차순인 경우에는 최대값 반환

(자바의 util 패키지를 import 해야한다.)

 

사용방법

// 선언
val pq = PriorityQueue<Type>()

// 삽입
pq.add(...)
pq.addAll(...)
pq.offer(...)

// 삭제
pq.poll()
pq.remove()

// 탐색
pq.contains(...)
pq.size
pq.peek()

삽입, 삭제 모두 O(logN)의 시간복잡도를 가진다.(부모노드만 비교하며 절반씩 비교하는 횟수를 줄여가기 때문이다.)

*물론 특정 원소를 삭제하는 건 O(logN)이 아니다.(먼저 탐색을 해야하기 때문이다.)

 

우선순위 설정

자료형이 원시 자료형 하나라면 아무 조건이 없는 경우 오름차순으로 정렬되고 reverseOrder()를 사용하면 내림차순으로 정렬된다.

// 오름차순
val pq = PriorityQueue<Int>()

// 내림차순
val pq2 = PriorityQueue<Int>(reverseOrder())

 

하지만 Pair나 Triple 또는 Data Class라면 아무 조건이 없을 때 에러가 발생한다.

어떤 값을 기준으로 정렬을 해야할지 정해져있지 않기 때문이다.

 

Pair나 Triple의 경우에 첫번째 값을 기준으로 오름차순을 하고 싶다면

// 방법 1
val pq = PriorityQueue<Pair<Int, Int>>(Comparator { a, b -> a.first - b.first })
val pq = PriorityQueue<Triple<Int, Int, Int>>(Comparator { a, b -> a.first - b.first })

// 방법 2
val pq = PriorityQueue<Pair<Int, Int>>({ a, b -> a.first - b.first })
val pq = PriorityQueue<Triple<Int, Int, Int>>({ a, b -> a.first - b.first })

// 방법 3
val pq = PriorityQueue<Pair<Int, Int>> { a, b -> a.first - b.first }
val pq = PriorityQueue<Triple<Int, Int, Int>> { a, b -> a.first - b.first }

// 방법 4
val pq = PriorityQueue<Pair<Int, Int>> { a, b -> a.first.compareTo(b.first) }
val pq = PriorityQueue<Triple<Int, Int, Int>> { a, b -> a.first.compareTo(b.first) }

이런 방법이 있고 내림차순으로 하고 싶다면 a.first와 b.first의 위치를 바꾸면 된다.

 

Data Class의 경우에는 클래스를 만들 때 Comparable을 상속받는 방식과 초기화할 때 고차함수를 사용하는 방식이 있다.

// 방법 1 : 상속
data class Node(
    val endPoint: Int,
    val cost: Int
): Comparable<Node> {
    override fun compareTo(other: Node): Int = cost - other.cost
}

fun main() {
    val pq = PriorityQueue<Node>()
}

// 방법 2 : 고차함수
fun main() {
    val pq = PriorityQueue<Node> { p1, p2 ->
        when {
            p1.cost > p2.cost -> 1
            p1.cost < p2.cost -> -1
            else -> 0
        }
    }
}

고차함수로 하면 사용하는 부분에서 바로 비교가 가능하고 수정이 가능하기 때문에 좋긴 하지만 코드가 늘어나고 다른 곳에서 새롭게 우선순위큐를 만들어 사용할 때마다 람다식을 붙여줘야한다는 불편한 점이 있다.

 

사용 예시

작업 스케줄링

다익스트라 알고리즘

A* 알고리즘

허프만 코딩