[Algorithm] 우선순위 큐(Priority Queue)란? (Kotlin)

정렬 알고리즘 1에서 힙 정렬을 확인할 때 이진 트리, 우선순위 큐를 알아야 힙을 알 수 있다고 했었다. 이 포스팅에선 우선순위 큐부터 무엇인지 알아보고 코틀린으로 구현한 예시를 확인한다.

아래는 우선순위 큐에 대한 영문 위키백과다.

 

https://en.wikipedia.org/wiki/Priority_queue

Priority queue - Wikipedia

우선순위 큐는 일반 큐 또는 스택과 유사한 추상 데이터 유형이다. 우선순위 큐의 각 요소에는 연관된 우선순위가 있다. 우선순위가 높은 요소가 낮은 요소보다 먼저 제공된다. 일부 구현에선 두 요소의 우선순위가 같으면 대기열에 추가된 순서와 같은 순서로 제공된다. 다른 구현에선 우선순위가 같은 요소의 순서가 정의되지 않는다
우선순위 큐는 힙을 써서 구현되는 경우가 많지만 개념적으로 힙과 구별된다. 우선순위 큐는 리스트, 맵 같은 추상적인 데이터 유형으로 리스트가 링크드 리스트배열로 구현될 수 있는 것처럼 우선순위 큐도 힙이나 정렬된 배열 같은 다른 방법으로 구현될 수 있다. 우선순위 큐는 최소한 아래 작업들을 지원해야 한다

- isEmpty
- insertWithPriority : 연결된 우선순위를 가진 요소를 대기열에 추가
- pullHighestPriorityElement : 우선순위가 가장 높은 대기열에서 요소를 제거하고 리턴. 이 함수는 popElement(off), getMaximumElement 또는 getFront(Most)Element라고도 한다...(중략)

또한 우선순위가 가장 높은 요소를 리턴하지만 큐를 수정하지 않는 peek은 매우 자주 구현되며 거의 항상 O(1) 시간 안에 실행된다. 이 연산과 O(1) 성능은 우선순위 큐의 많은 앱에서 매우 중요하다. 고급 구현에선 우선순위가 가장 높거나 낮은 처음 몇 개의 요소 검사, 큐 지우기, 큐의 하위 집합 지우기, 일괄 삽입 수행, 둘 이상의 큐를 하나로 병합, 모든 요소의 우선순위 증가 등 같은 더 복잡한 작업을 지원할 수 있다. 스택, 큐는 특정 종류의 우선순위 큐로 구현할 수 있으며 우선순위는 요소가 삽입되는 순서에 따라 결정된다
스택에선 삽입된 각 요소의 우선순위가 단조롭게 증가하므로 마지막에 삽입된 요소가 항상 맨 먼저 검색된다. 큐에선 삽입된 각 요소의 우선순위가 단조롭게 감소하므로, 처음 삽입된 요소가 항상 가장 먼저 검색된다...(중략)

 

밑으로 내리면 수도코드 형태로 우선순위 큐를 간단하게 구현하는 방법을 적어둔 게 있다.

우선순위 큐는 내부적으로 힙 자료구조를 사용해서 요소들의 우선순위를 관리한다. 그럼 힙 자료구조는 무엇인가?

 

https://en.wikipedia.org/wiki/Heap_(data_structure)

Heap (data structure) - Wikipedia

힙은 힙 속성을 만족하는 트리 기반 데이터 구조다. 최대 힙에서 주어진 노드 C에 대해 P가 C의 부모 노드라면 P의 키(값)는 C의 키보다 크거나 같고, 최소 힙에서 P의 키는 C의 키보다 작거나 같다. 힙의 최상위 노드(부모 노드가 없는 노드)에 있는 노드를 루트 노드라고 한다
힙은 우선순위 큐라는 추상적 데이터 유형을 최대한 효율적으로 구현한 것으로, 실제로 우선순위 큐는 구현 방식에 상관없이 종종 힙이라고 불린다. 힙에선 우선순위가 가장 높은(또는 낮은) 요소가 항상 루트에 저장된다. 그러나 힙은 정렬된 구조가 아니며 부분 정렬된 것으로 간주할 수 있다. 힙은 우선순위가 가장 높은(또는 낮은) 객체를 반복 제거해야 하거나 루트 노드의 제거, 삽입이 산재돼 있어야 할 때 유용한 데이터 구조다. 힙의 일반적인 구현은 트리가 완전한 이진 트리인 바이너리 힙이다

힙 자료구조, 특히 바이너리 힙은 1964년 J. W. J Williams가 힙 정렬 알고리즘의 자료구조로 도입했다. 힙은 다익스트라의 알고리즘 같은 여러 그래프 알고리즘에서도 중요한 역할을 한다. 힙이 완전한 이진 트리인 경우 힙은 가능한 가장 작은 높이를 가지며 N개의 노드가 있고 각 노드의 분기는 항상 log N의 높이를 갖는다. 형제 또는 사촌 간의 암시적 순서가 없으며 순서에 따른 탐색(이진 검색 트리 등)에 대한 암시적 순서가 없단 것에 주의하라. 앞에서 언급한 힙 관계는 노드와 부모 노드, 조부모 노드 사이에만 적용된다
각 노드가 가질 수 있는 최대 자식 수는 힙의 유형에 따라 다르다. 힙은 일반적으로 요소가 저장된 같은 배열에서 제자리에 구성되며, 그 구조는 연산의 접근 패턴에 내포돼 있다. 힙은 키 저장에 쓰이는 메모리 외에 추가 메모리가 필요없다는 점에서 기수 트리(Radix Tree)와 같이 이론적 경계가 비슷하거나 경우에 따라 더 나은 자료구조와 다르다
힙의 일반적인 작업은 아래와 같다

- findMax(또는 findMin) : 최대 힙의 최대 항목 or 최소 힙의 최소 항목을 각각 찾는다(≒peek)
- insert : 힙에 새 키를 추가(≒push)
- extractMax(또는 extractMin) : 힙에서 최대(최소)값을 제거한 후 최대 힙에서 최대값 노드(또는 최소 힙에서 최소값 노드)를 리턴(≒pop)
...(중략)

 

힙은 트리 기반의 완전 이진 트리고 어떤 우선순위 규칙에 따라 부모, 자식 노드 간의 관계가 정의되는 자료구조다. 주로 우선순위 큐에서 쓰이며 최대값, 최소값을 빠르게 찾고 제거하는 작업에 적합하다. 최대값이나 최소값에 빠르게 접근할 때마다 힙 자료구조를 쓰면 그 항목은 항상 배열의 첫 번째 위치 또는 루트 노드에 위치하게 된다.

그러나 정렬된 구조가 아니기 때문에 첫 요소를 제외한 나머지는 정렬되지 않은 상태로 유지된다. 따라서 가장 크거나 작은 요소에만 즉시 접근이 가능하다. 이런 특징으로 인해 힙에서 가장 중요한 연산은 삽입, 제거다.

아래는 코틀린으로 최소 힙 자료구조를 구현한 예시다.

 

class MinHeap {
    private val heap = mutableListOf<Int>()

    // 힙에 새 요소 삽입 (sift up 과정 포함)
    fun insert(value: Int) {
        heap.add(value) // 새 요소는 트리 맨 끝에 삽입
        siftUp(heap.size - 1) // 힙 속성 유지
    }

    // 최상위 요소 삭제, 반환 (sift down 과정 포함)
    fun remove(): Int? {
        if (heap.isEmpty()) return null     // 빈 리스트 처리
        val rootValue = heap[0]             // 루트 노드 (최소값)
        if (heap.size == 1) {               // 요소가 하나뿐이면 바로 제거
            return heap.removeAt(0)
        }
        heap[0] = heap[heap.size - 1]       // 루트로 마지막 요소 이동
        heap.removeAt(heap.size - 1)  // 마지막 요소 제거
        siftDown(0) // 힙 속성 유지
        return rootValue
    }

    // 힙의 최상위 요소 확인 (제거x)
    fun peek(): Int? {
        return if (heap.isNotEmpty()) heap[0] else null
    }

    fun isEmpty(): Boolean {
        return heap.isEmpty()
    }

    // 부모 노드와 비교해서 힙 속성을 유지
    private fun siftUp(index: Int) {
        var childIndex = index
        val childValue = heap[childIndex]
        var parentIndex = (childIndex - 1) / 2

        // 부모가 자식보다 크면 부모와 교환
        while (childIndex > 0 && heap[parentIndex] > childValue) {
            heap[childIndex] = heap[parentIndex] // 부모 노드를 자식 위치로 내림
            childIndex = parentIndex
            parentIndex = (childIndex - 1) / 2
        }
        heap[childIndex] = childValue // 자식 값을 최종 위치에 삽입
    }

    // 자식 노드들과 비교하여 힙 속성을 유지
    private fun siftDown(index: Int) {
        var parentIndex = index
        val parentValue = heap[parentIndex]
        val size = heap.size

        while (true) {
            val leftChildIndex = 2 * parentIndex + 1
            val rightChildIndex = 2 * parentIndex + 2
            var smallestIndex = parentIndex

            // 왼쪽 자식이 부모보다 작으면 왼쪽 자식 선택
            if (leftChildIndex < size && heap[leftChildIndex] < heap[smallestIndex]) {
                smallestIndex = leftChildIndex
            }

            // 오른쪽 자식이 부모, 왼쪽 자식보다 작으면 오른쪽 자식 선택
            if (rightChildIndex < size && heap[rightChildIndex] < heap[smallestIndex]) {
                smallestIndex = rightChildIndex
            }

            // 자식들이 부모보다 크면 힙 속성이 유지 완료된 것
            if (smallestIndex == parentIndex) break

            // 부모와 가장 작은 자식의 위치를 서로 교환
            heap[parentIndex] = heap[smallestIndex]
            parentIndex = smallestIndex
        }

        heap[parentIndex] = parentValue // 부모 노드를 최종 위치에 삽입
    }
}

fun main() {
    val minHeap = MinHeap()

    minHeap.insert(10)
    minHeap.insert(4)
    minHeap.insert(15)
    minHeap.insert(20)
    minHeap.insert(0)
    minHeap.insert(8)

    // 힙의 최상위 요소 확인
    println("Top element: ${minHeap.peek()}")

    // 요소 제거 (최소값부터 제거)
    while (!minHeap.isEmpty()) {
        println("Removed element: ${minHeap.remove()}")
    }
}

// Top element: 0
// Removed element: 0
// Removed element: 4
// Removed element: 8
// Removed element: 10
// Removed element: 15
// Removed element: 20

 

이제 코틀린으로 우선순위 큐를 구현한 예시를 확인한다. 코틀린에선 java.util.PriorityQueue 패키지를 임포트해서 위처럼 직접 힙 자료구조를 구현하지 않아도 사용할 수 있다.

아래는 코틀린으로 우선순위 큐를 구현한 예시다. 위와 동일하게 최소 힙을 사용한 예시다.

 

import java.util.PriorityQueue

class CustomPriorityQueue<T>(private val comparator: Comparator<T>) {
    private val heap = PriorityQueue(comparator)

    fun add(element: T) {
        heap.add(element)
    }

    // 최상위 요소 제거, 반환
    fun poll(): T? {
        return heap.poll()
    }

    // 최상위 요소 확인 (제거하지 않음)
    fun peek(): T? {
        return heap.peek()
    }

    fun isEmpty(): Boolean {
        return heap.isEmpty()
    }

    fun size(): Int {
        return heap.size
    }
}

fun main() {
    // 숫자가 작은 순서대로 우선순위 큐에서 먼저 처리되게 설정
    // = 작은 숫자가 더 높은 우선순위를 가짐
    val comparator = Comparator<Int> { a, b -> a - b }
    val priorityQueue = CustomPriorityQueue(comparator)

    priorityQueue.add(5)
    priorityQueue.add(1)
    priorityQueue.add(3)
    priorityQueue.add(10)

    println("현재 큐 크기 : ${priorityQueue.size()}")
    println("최상위 요소 : ${priorityQueue.peek()}")
    println("peek() 후 큐 크기 : ${priorityQueue.size()}")
    println("============================================================")

    // 모든 요소 출력 및 제거
    while (!priorityQueue.isEmpty()) {
        println("poll() : ${priorityQueue.poll()}")
        println("poll() 후 큐 크기 : ${priorityQueue.size()}")
    }
}

// 현재 큐 크기 : 4
// 최상위 요소 : 1
// peek() 후 큐 크기 : 4
// ============================================================
// poll() : 1
// poll() 후 큐 크기 : 3
// poll() : 3
// poll() 후 큐 크기 : 2
// poll() : 5
// poll() 후 큐 크기 : 1
// poll() : 10
// poll() 후 큐 크기 : 0

 

커스텀 우선순위 큐를 만들면서 java.util.PriorityQueue를 사용했다. 이 패키지를 사용하지 않으면 힙 자료구조를 직접 구현해야 하는데, 우선 예시 코드부터 먼저 확인한다.

CustomPriorityQueue 클래스 안에서 먼저 PriorityQueue 인스턴스를 만들고 add, poll, peek, isEmpty, size()를 구현하는 걸 볼 수 있다. 여기서 참고할 것은 add()는 insertWithPriority를 구현한 것이고, poll()은 pullHighestPriorityElement를 구현한 것이다.

위키백과에 쓰인 함수들은 우선순위 큐의 핵심 기능을 설명하는 이름일 뿐이고 코틀린을 비롯한 다른 언어에서 반드시 같은 이름으로 구현돼야 할 필요는 없다. 본질적으로 같은 기능을 제공하기 때문이다.

add() 안의 add()를 클릭하면 PriorityQueue의 add()로 이동한다.

 

/**
 * 지정된 요소를 우선순위 큐에 삽입한다
 *
 * @return {@code true} (as specified by {@link Collection#add})
 * @throws ClassCastException 지정된 요소를 우선순위 큐의 순서에 따라
 *         현재 이 우선순위 큐에 있는 요소와 비교할 수 없는 경우
 * @throws NullPointerException 지정된 요소가 null인 경우
 */
public boolean add(E e) {
    return offer(e);
}

/**
 * 지정된 요소를 우선순위 큐에 삽입한다
 *
 * @return {@code true} (as specified by {@link Queue#offer})
 * @throws ClassCastException 지정된 요소를 우선순위 큐의 순서에 따라
 *         현재 이 우선순위 큐에 있는 요소와 비교할 수 없는 경우
 * @throws NullPointerException 지정된 요소가 null인 경우
 */
public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    siftUp(i, e);
    size = i + 1;
    return true;
}

 

add()는 내부적으로 offer()를 사용하는데, 이 중 siftUp(i, e)가 우선순위에 따라 힙에 요소를 저장하는 메서드다.

 

/**
 * 항목 x를 위치 k에 삽입하고, x가 상위 항목보다 크거나 같거나 루트가 될 때까지
 * 트리 위로 승격시켜 힙 불변성을 유지한다
 *
 * 강제, 비교를 단순화하고 속도를 높이기 위해 Comparable와 Comparator 버전은
 * 서로 다른 메서드로 분리돼 있지만 그 외에는 동일하다. siftDown도 마찬가지다
 *
 * @param k 채울 위치
 * @param x 삽입할 항목
 */
private void siftUp(int k, E x) {
    if (comparator != null)
        siftUpUsingComparator(k, x, queue, comparator);
    else
        siftUpComparable(k, x, queue);
}

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable<? super T> key = (Comparable<? super T>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (key.compareTo((T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = key;
}

private static <T> void siftUpUsingComparator(
    int k, T x, Object[] es, Comparator<? super T> cmp) {
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = es[parent];
        if (cmp.compare(x, (T) e) >= 0)
            break;
        es[k] = e;
        k = parent;
    }
    es[k] = x;
}