cs log

Priority Queue

· cs

우선순위 큐란?

  • 큐와 다르게 FIFO(선입선출) 하는 구조가 아니라 우선순위가 높은 순서에 따라 원소를 반환한다.
  • 큐도 먼저 삽입된 원소가 우선순위가 더 높은 일종의 우선순위큐로도 생각해볼 수 있다.
  • 보통 이진힙(Binary Heap)으로 구현된다.

이진힙(Binary Heap)

  • 완전이진트리로서 부모노드의 우선순위가 자식노드의 우선순위보다 높은 자료구조
  • Minimum Heap(최소힙) : 키값이 작을수록 높은 우선순위를 가짐
  • Maximum Heap(최대힙) : 키값이 클수록 높은 우선순위를 가짐

이진힙의 구현

  • 1차원 리스트를 활용해 구현할 수 있다. 1차원 리스트에서 두번째 원소부터 사용하여 구현한다.
  • 완전이진트리의 노드를 레벨순회(Level-Order Traversal) 방향으로 배열에 차례대로 저장한다.
[1] 완전이진트리의 1차원 리스트 표현
  • 배열을 x라고 하였을떄 i번쨰 노드(원소)가 가지는 특징은 다음과 같다.
1. x[i] 의 자식노드는 x[2i] , x[2i+1] 에 위치한다.
2. x[i] 의 부모노드는 x[i//2]에 위치한다. (단, i가 루트노드가 아닌 경우)

이진힙의 연산

  • 이진힙은 항상 부모노드의 우선순위가 자식노드의 우선순위보다 높아야 한다. 때문에 heap에 원소를 넣거나, 뺼떄 이 규칙을 준수하도록 연산이 이루어져야 한다. 이떄 heap 내 원소 교환 연산이 이루어지는 방향에 따라 downheap,upheap으로 나눌 수 있다.

핵심 연산

  • downheap 연산 : 부모노드에서 자식노드 방향으로 내려가면서 , 왼쪽자식노드와 오른쪽자식노드간 우선순위가 더 높은 승자를 뽑는다. 그리고 승자자식노드를 부모노드와 교환한다.
  • upheap 연산 : 자식노드에서 부모노드 방향으로 올라가면서 , 자식노드의 우선순위가 더 높다면 부모노드와 교환

이진힙의 구현 예시

  • 이진힙을 1차원 리스트를 활용해 구현하면 다음과 같다. (최소 힙 구현이며, 최대 힙은 각 원소의 -1을 곱해주면 구현이 가능하다)
  • insert시 upheap 연산을 수행하면서, 리프 노드에서 부모노드 방향으로 우선순위 정합성을 지키도록 연산이 이루어진다.
  • pop시 downheap 연산을 수행하면서, 루트노드에서 리프노드 방향으로 우선순위 정합성을 지키도록 연산이 이루어진다.
public class BinaryHeap {

    private int[] heap;

    private int size;

    public BinaryHeap(int capacity) {
        this.heap = new int[capacity];
        this.size = 0;
    }

    public void insert(int value) {
        size++;
        if (size >= this.heap.length) {
            this.heap = Arrays.copyOf(heap, heap.length * 2);
        }
        heap[size] = value;
        upHeap(size);
    }

    public int pop() {
        if (size == 0) {
            throw new IllegalStateException("heap is empty");
        }
        int root = heap[1];
        heap[1] = heap[size];
        heap[size--] = 0;
        downHeap(1);
        return root;
    }

    private void downHeap(int index) {
        while (2 * index <= size) {
            int k = 2 * index;
            if (k < size && heap[k] > heap[k + 1]) {
                k += 1;
            }
            if (heap[index] < heap[k] || heap[k] == 0) {
                break;
            }
            int tmp = heap[index];
            heap[index] = heap[k];
            heap[k] = tmp;
            index = k;
        }
    }

    private void upHeap(int index) {
        while (index > 1 && heap[index / 2] > heap[index]) {
            int tmp = heap[index / 2];
            heap[index / 2] = heap[index];
            heap[index] = tmp;
            index /= 2;
        }
    }
}

class BinaryHeapTest {

    @Test
    public void should_pop_top_priority_element() {
        BinaryHeap heap = new BinaryHeap(5);

        List<Integer> input = List.of(17, 3, 2, 1, 59, 6, 23, 12, 32);
        for (int value : input) {
            heap.insert(value);
        }
        List<Integer> sortedInput = input.stream().sorted().toList();
        for (Integer value : sortedInput) {
            assertThat(heap.pop()).isEqualTo(value);
        }
        assertThatThrownBy(heap::pop);
    }
}

연산 시간복잡도

  • 우선순위가 가장 높은 원소에 접근 : O(1)
  • 삼입/삭제 연산 : 힙의 높이, 즉 완전이진트리의 깊이에 비례한다. O(logN)

Java Built-In Library

  • java 에서는 우선순위큐를 직접 구현할 필요없이 구현체를 제공하고 있다.
java.util.PriorityQueue

우선순위 자료구조를 활용한 코딩테스트 문제

Reference

[1] https://runestone.academy/ns/books/published/pythonds/Trees/BinaryHeapImplementation.html