우선순위 큐 (Kotlin 구현 포함)

09.03.2022 — 개발, 자료구조 — 1 min read

개요

Priority Queue는 enqueue할 때는 아무거나 들어오지만 dequeue할 때는 가장 우선순위가 높은 것부터 빠져나갑니다. 보통 Heap으로 구현합니다. 물론 Heap 외에도 여러가지 방법으로 구현할 수 있지만 Heap이 가장 성능 효율이 좋습니다.

하지만, 주로 제품과 서비스를 개발해온 개발자 입장에서 여태까지 실무에서 이 자료구조를 사용해본 경험은 거의 없습니다. 만약 사용한다고 하더라도, RabbitMQ 처럼 이 자료구조를 구현한 다른 라이브러리를 쓰게 됩니다.

배열로 구현하는 경우

우선 순위가 가장 높은 원소를 dequeue 할 때마다 찾아야 한다면 모든 원소를 탐색해야 합니다.

Enqueue: O(1)
Dequeue: O(n)

링크드 리스트로 구현하는 경우

배열이랑 다를 게 없습니다. 만약 삽입할 때 우선순위가 가장 높은 원소가 가장 앞으로 오도록 구현하더라도 삽입시 O(n), 인출 시 O(1)이 되는 것 뿐입니다.

Enqueue: O(1)
Dequeue: O(n)

힙으로 구현하는 경우

삽입이나 인출이 일어날 때마다 부모와 자식의 키를 비교하여 완전 이진 트리로 만드는 과정을 거치기 때문에 성능이 좋습니다.

Enqueue: O(log(n))
Dequeue: O(log(n))

구현(Kotlin) - Max Heap

코틀린으로 구현해보면 다음과 같습니다.

priority_queue

1fun main() {
2
3    class Heap {
4        private val array = mutableListOf<Int>()
5
6        fun insert(e: Int) {
7            array.add(e)
8            heapifyOnInsert(e, array.lastIndex)
9        }
10
11        private fun heapifyOnInsert(newE: Int, newIndex: Int) {
12            val parentIndex = getParentIndex(newIndex)
13            if (array[parentIndex] < newE) {
14                array[newIndex] = array[parentIndex]
15                array[parentIndex] = newE
16                heapifyOnInsert(newE, parentIndex)
17            }
18        }
19
20        fun delete(): Int? {
21            val root = array.firstOrNull() ?: return null
22            heapifyOnDelete(0)
23            array.removeLast()
24            return root
25        }
26
27        private fun heapifyOnDelete(emptyIndex: Int) {
28            val left = getLeftChildIndex(emptyIndex)
29            val right = getRightChildIndex(emptyIndex)
30            if (left <= array.lastIndex && right <= array.lastIndex) {
31                if (array[left] > array[right]) {
32                    array[emptyIndex] = array[left]
33                    heapifyOnDelete(left)
34                } else {
35                    array[emptyIndex] = array[right]
36                    heapifyOnDelete(right)
37                }
38                return
39            }
40
41            if (left <= array.lastIndex) {
42                array[emptyIndex] = array[left]
43                return
44            }
45
46            if (right <= array.lastIndex) {
47                array[emptyIndex] = array[right]
48                return
49            }
50
51            if (emptyIndex != array.lastIndex) {
52                array[emptyIndex] = array.last()
53            }
54        }
55
56        private fun getLeftChildIndex(idx: Int): Int {
57            return (idx + 1) * 2 - 1
58        }
59
60        private fun getRightChildIndex(idx: Int): Int {
61            return (idx + 1) * 2
62        }
63
64        private fun getParentIndex(idx: Int): Int {
65            return (idx - 1) / 2
66        }
67
68        override fun toString(): String {
69            return array.toString()
70        }
71    }
72
73
74    val heap = Heap()
75    heap.insert(1)
76    heap.insert(3)
77    heap.insert(4)
78    heap.insert(5)
79    heap.insert(2)
80    heap.insert(7)
81    heap.insert(6)
82    println(heap.toString())
83    heap.delete()
84    println(heap.toString())
85    heap.delete()
86    println(heap.toString())
87    heap.delete()
88    println(heap.toString())
89    heap.delete()
90    println(heap.toString())
91    heap.delete()
92    println(heap.toString())
93}