Priority Queue

우선순위 큐

우선순위 큐는 힙(Heap) 자료구조로 구현되어 있으며, 우선순위 큐에서 비교 대상을 무엇으로 결정하느냐에 따라 최소힙과 최대힙으로 나뉜다. 최소힙과 최대힙은 각각 아래의 특성을 유지한다.

최소힙

• 루트 노드는 트리에서 가장 작은 값이다.
• 부모 노드는 자식 노드보다 항상 작은 값이다.

최대힙

• 루트 노드는 트리에서 가장 큰 값이다.
• 부모 노드는 자식 노드보다 항상 큰 값이다.

시간 복잡도

설명은 최소힙 기준이다.

최솟값 탐색

최소힙에서 가장 작은 값을 확인할 때 $ O(1) $ 의 시간이 소요된다. 가장 작은 값이 항상 루트에 있어서 루트 노드만 확인하면 된다.

삽입

값을 추가할 때는 $ O(log N) $ 의 시간이 소요된다. 새로운 노드는 항상 마지막 위치에 추가하게 되는데 이때 추가되는 노드로 인해 heap의 특성이 깨질 수 있고 heap의 특성을 맞춰주기 위해서 heapify라는 과정을 수행한다.

예를 들어 최소힙에 3이라는 값만 있을 때 1을 추가하면 (1이 루트에 있어야 하므로)힙의 성질이 깨지게 된다.
따라서 heapify 과정을 통해 새로 추가된 노드(1)와 추가된 노드의 부모 노드(3) 값을 확인하고, 새로 추가된 노드 값이 부모 노드의 값보다 작다면 둘의 위치를 바꾸어주는 과정을 heap 성질이 만족될 때까지 수행하는 것이다.

삭제

값을 삭제하는 경우에도 $ O(log N) $ 의 시간이 소요된다. 값의 삭제는 루트 노드에서만 발생하고, 일단 삭제된 루트 노드의 위치에는 힙에서 가장 마지막 노드로 채운다.

이렇게 채워진 루트 노드가 힙의 성질을 만족하지 않을 수 있기 때문에 루트(부모) 노드의 왼쪽 자식 노드와 오른쪽 자식 노드 중에서 어느 노드를 부모 노드 위치와 바꿀 것인지 결정해야 하고, 단말 노드까지 내려가면서 heapify 과정을 수행한다.

예를 들어 최소힙이 [1, 2, 3, 4]로 구성되어 있을 때 루트(부모) 노드 값(1)이 삭제되면,
가장 마지막 위치에 있는 4가 루트 노드 자리로 올라온다.
[4, 2, 3]
최소힙의 성질을 만족하지 않기 때문에 heapify 과정을 수행해야 하고, 
이때 왼쪽 자식 노드의 값(2)이 오른쪽 자식 노드의 값(3)보다 작으므로
왼쪽 자식 노드와 부모 노드의 위치를 바꾼다.
[2, 4, 3]
결과적으로 위처럼 최소힙 성질을 만족하게 된다.

특정 데이터 탐색

힙 자료구조에서 특정 데이터를 탐색하려면 $ O(N) $ 의 시간이 소요된다.

Red-Black-Tree 등의 구조를 채택한 Map(TreeMap)과는 달리, 힙이 전체 데이터에 대해 정렬 구조를 이루지는 않기 때문에 특정 값이 존재하는지 확인하려면 모든 데이터를 확인해야 한다.

코드로 구현해 보는 우선순위 큐

관련된 알고리즘 문제는 1927번(최소힙)이다. 큐의 전체 사이즈를 미리 결정한 정적 힙 방식을 사용했다.

https://www.acmicpc.net/problem/1927

삽입

값을 마지막 위치에 추가한다.

추가된 노드(now)와 그 노드의 부모 노드(parent)를 확인하여 힙의 성질을 만족시키는 heapify 과정을 수행한다.

private static void push(int x) {
    queue[++qSize] = x;
    // queue[i] : now
    // queue[i >> 1] : parent
    // queue[i] < queue[i >> 1] : (swap) Because queue is min-heap.
    for (int i = qSize; i > 1 && queue[i] < queue[i >> 1]; i >>= 1) {
        int tmp = queue[i];
        queue[i] = queue[i >> 1];
        queue[i >> 1] = tmp;
    }
}

삭제

최솟값은 항상 루트에 있으므로 반환해야 할 값은 queue[1]이다.

일단 삭제된 루트 노드의 위치에는 힙에서 가장 마지막 노드로 채운다. queue[1] = queue[qSize--]

이렇게 채워진 루트 노드가 힙의 성질을 만족하지 않을 수 있기 때문에 새로 추가된 루트(부모) 노드의 왼쪽 자식 노드와 오른쪽 자식 노드 중에서 어느 노드를 부모 노드 위치와 바꿀 것인지 결정해야 하고, 단말 노드까지 내려가면서 heapify 과정을 수행한다.

private static int pop() {
    if (qSize == 0) return 0;
    int ret = queue[1];
    queue[1] = queue[qSize--];

    int t;
    for (int i = 1; (i << 1) <= qSize; ) {
        int left = i << 1;
        int right = left + 1;
        if (queue[left] < queue[right] || right > qSize) {
            t = left;
        } else {
            t = right;
        }

        if (queue[t] < queue[i]) {
            int tmp = queue[t];
            queue[t] = queue[i];
            queue[i] = tmp;
            i = t;
        } else {
            break;
        }
    }
    return ret;
}