[알고리즘] Priority Queues 우선순위 큐: 필수 기본 정리 - 구현, 활용, comparable, comparator

목차

선입선출/후입선출

우리는 이전 포스트 들에서 선입선출 FIFO 후입 선출 LIFO 와 같은 큐의 순서를 알아봤습니다. 새로 배우는 우선순위 큐도 이 큐들 중 한 종류입니다. 

 

우선순위 큐(Priority Queue) 개념

일반적으로 쓰이는 queue에서는 선입선출(FIFO)과 다르게 특정 기준 순서로 아이템이 큐에서 빠지게 됩니다. 예를 들면 리스트에서 가장 큰 값 먼저 dequeue 될 수 있고 작은 값 먼저 dequeue 될 수 있습니다. 이러한 기준을 정하여 queue를 생성할 수 있는 것이 우선순위 큐의 특징입니다.  

 

우선순위 큐는 두 가지 형태를 가지고 있을 수 있습니다. 

1. Max-Priority : 가장 우선순위에있는 element는 가장 큰 값

2. Min-Priority :  가장 우선순위에있는 element는 가장 작은 값

이처럼 우선순위큐는 최댓값과 최솟값을 찾을 때 효율적입니다. 

 

우선순위 큐 활용도

우선순위큐는 아래 상황들에서 사용됩니다. 
1. 다익스트라 알고리즘(Dijkstra’s algorithm) : 최소 값을 찾을 때 우선순위 큐가 사용됩니다. 

2. A* 알고리즘 : 출발지점부터 꼭짓점 까지 가는 최단 거리를 찾아줍니다. 

3. 힙정렬: 많은 힙 정렬에서는 우선순위 큐를 사용합니다. 

4. 허프만 코딩: 문자열을 트리를 이용해 2진수로 압축하는 알고리즘이고 min-Priority를 사용합니다. 

 

우선순위 큐 구현

우선순위 큐는 큐와 같은 목적으로 쓰이기 때문에, 큐에서 element가 나가는 방식과 순서를 제외한 모든 기능이 같습니다. 그러므로 우선순위 큐의 이전 포스트에서 다뤘던 Queue인터페이스를 사용하게 됩니다.

interface Queue<T> {
	fun enqueue(element: T): Boolean
    
    fun dequeue():T?
    
    val count: Int
    	get
    val isEmpty: Boolean
    	get() = count == 0
    fun peek(): T?
}

queue인터페이스에 자세한 설명은 아래 포스트를 확인해주세요. 

[알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐),ArrayList, Stack으

priority queue를 만드는 여러 가지 방법이 있습니다. 

1. Sorted Array: 최대 최솟값을 찾는데 좋지만 O(1), 삽입 과정은 비효율적입니다. 왜냐하면 삽입할 위치를 찾을 때, element를 하나씩 모두 접근해야 하기 때문에 O(n) 속도를 가집니다. 

2. Balanced Binary Search Tree : 이중 우선순위 큐를 만들 때 효율적입니다. min과 max를 찾을 때, 삽입할 때 모두 O(logn)을 가집니다. 

3. Heap: 힙을 사용하는 것이 우선순위 큐를 만들 때 가장 일반적인 선택입니다. sorted Array는 모든 element가 정렬되야하지만, heap은 부분적으로 정렬되면 되기 때문이다. 힙에 모든 오퍼레이션은 O(log n) 속도를 가집니다. 하지만 min max 찾을 때는 가장 빠른 O(1) 속도를 가집니다. 

 

 

이제 힙을 이용해서 우선순위 큐를 만드는 법을 알아보겠습니다. 시작하기 전 힙에 대하여 자세히 알고 싶으시다면 아래 포스트를 참고해주세요. 

[알고리즘] Heap 힙 데이터구조 : 필수 기본정리 - Min Heap, Max Heap, 삽입, 제거, 탐색 구현

 

우선순위 큐 클래스 생성

먼저 우선순위 큐 추상 클래스를 생성해주겠습니다. 위에서 heap을 사용했을때 가장 효율적이기때문에 힙을 사용하고, 우선순위큐 추상 클래스에 queue인터페이스를 적용하여 enqueue, dequeue, count, peek과 같은 함수를 오버라이드 해주겠습니다. 

//1
abstact class AbstractPriorityQueue<T> : Queue<T>{
	//2
    abstract val heap: Heap<T>
    	get
    //A
    override fun enqueue(element:T): Boolean{
    	heap.insert(element)
        return true
    }
    
    //B
    override fun dequeue() = heap.remove()
    
    //C
    override val count: Int
    	get() = heap.count
    //D
    override fun peek() = heap.peek()
}

코드를 설명해보겠습니다. 

1. 우선순위 큐 추상 클래스는 Queue인터페이스를 기본으로 합니다. 

2. 그리고 Heap <T>를 쓰게 됩니다. 

A. enqueue 함수를 실행하면 heap에서 insert를 쓰게됩니다. O(log n)의 속도를 가집니다. 

B. dequeue 함수를 실행하면 heap에서 remove를 실행합니다. heap은 가장 우선순위에 있는 것을 O(log n)으로 찾아서 삭제를 도와줍니다. 

C. Count는 heap이 쓰는 카운트와 같습니다. 

D. Peek 또한 같습니다. 가장 위에 있는 값을 찾아줍니다. 

 

Comparable 사용하기

comparable은 자기 자신과 매개변수 객체를 비교합니다. comparable을 통해 값을 비교하는 인터페이스를 가져올 수 있게 되었습니다. 

class ComparablePriorityQueueImpl<T : Comparable<T>> :
    AbstractPriorityQueue<T>() {
    override val heap = ComparableHeapImpl<T>()
}

이제 위 클래스를 이용해서 main문에서 실행해보겠습니다. 

"min priority queue" example{
	//1
    val stringLengthComparator = object: Comparator<String>{
    	override fun compare(o1: String, o2:String?): Int{
        	val length1 = o1?.length?: -1
            val length2 = o2?.length?: -1
            return length1 - length2
        }
    }
    //2
    val priorityQueue = ComparatorPriorityQueueImpl(stringLengthComparator)
    //3
    arrayListOf("one", "two", "three", "forty", "five", "six","seven", "eight", "nine").forEach{
    	priorityQueue.enqueue(it)
    }
    //4
    while(!priorityQueue.isEmpty) {
    	println(priorityQueue.dequeue())
    }
    
}

1. PriorityQueue안에 ComparablePriorityQueueImpl <Int> 정수 타입을 가진 데이터 구조가 들어와야 한다고 generic을 이용해 선언해줍니다. 

2. 정렬되지 않은 array를 priorityQueue.enqueue를 통해 정렬해서 넣어줍니다. 

3. 모든 값들을 dequeue 해서 값을 큐에서 제거해줍니다. 

위 코드를 실행해주면 다음과 같습니다. 

---Example of max priority queue---
12
8
7
6
4
3
1
1

가장큰 정수값부터 프린트된것을 확인할수있습니다. 

 

Comparator 사용하기

comparable은 자기 자신과 매개변수 객채를 비교하는 반면, comparator는 두 매개변수 객체를 비교하게 됩니다. 이번에는 comparator를 사용하여 우선순위 큐 클래스를 만들어보겠습니다. 

class ComparatorPriorityQueueImpl<T>(
	private val comparator:Comparator<T>
): AbstractPriorityQueue<T>(){
	override val heap = comparatorImpl(comparator)
}

comparable을 사용했을 때와 다른 점은 heap에서 comparatorImpl를 구현해준 후 comparator라는 매개변수를 받는 것을 볼 수 있습니다. 

"min priority queue" example {
     // 1
     val stringLengthComparator = object : Comparator<String> {
        override fun compare(o1: String?, o2: String?): Int {
           val length1 = o1?.length ?: -1
           val length2 = o2?.length ?: -1
        return length1 - length2
        }
     }
     // 2
     val priorityQueue = 
     ComparatorPriorityQueueImpl(stringLengthComparator)
     // 3
     arrayListOf("one", "two", "three", "forty", "five", "six", "seven", "eight", "nine").forEach
     priorityQueue.enqueue(it)
     }
     // 4
     while (!priorityQueue.isEmpty) {
        println(priorityQueue.dequeue())
     }
}

1. String의 길이가 긴 것부터 짧은 것까지 나열하는 comparator를 만들게 됩니다. 

2. comparator를 이용하여 queue를 생성해줍니다 

3. 절렬되이않은 list를 priorityQueue.enqueue를 통해 정렬해서 넣어줍니다. 

4. 큐에서 하나씩 제거해줍니다. 

결과는 다음과 같습니다. 

---Example of min priority queue---
forty
three
eight
seven
nine
five
two
one
six

string길이가 가장긴forty부터 dequeue된걸 확인할수있습니다. 

참고

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)