우선순위 큐 (Priority Queue)

우선순위 큐란?

큐는 먼저 들어오는 데이터가 먼저 나가는 선입선출 (FIFO) 형식의 자료구조지만 우선순위 큐는 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
우선순위 큐는 힙(Heap)을 이용하여 구현하는 것이 가장 효율적이다.

Heap이란?

완전이진트리 형태의 자료구조

완전이진트리는 마지막 레벨을 제외한 모든 레벨이 모두 채워져 있고 마지막 레벨은 왼쪽부터 채워져 있어야 함

최대 힙(Max Heap): 부모 노드의 키값이 자식 노드보다 큰 구조
최소 힙(Min Heap): 부모 노드의 키값이 자식 노드보다 작은 구조

배열로 힙을 표현할 때

• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
• 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2
  

우선순위 큐의 동작 원리

1. 삽입 연산

1. 트리의 말단 노드에 새로운 값을 삽입한다.
2. 말단부터 루트까지 트리를 거슬러 올라가면서 Heapify (up-heap) 작업을 수행한다.

   Heapify: Heap의 특성을 만족하도록 각 노드들의 위치를 조정하는 과정

Max Heap의 삽입 연산

void insert(int item) {
	int i = ++size;
    //heapify (up-heap)
    while(i > 1 && item > heap[i/2]) {
    	heap[i] = heap[i/2];
        i /= 2;
    }
    heap[i] = item;
}

2. 삭제 연산

1. 루트 노드를 삭제한다.
2. 말단 노드를 빈 자리에 가져온다.
3. 루트부터 말단까지 내려가면서 Heapify (down-heap) 작업을 수행한다.

Max Heap의 삭제 연산

int delete() {
    int item = heap[1];
    int temp = heap[size--];
    
    int parent = 1, child = 2;
    //heapify (down-heap)
    while(child <= size) {
    	if((child < size) && (heap[child] < heap[child+1]))
        	child++;
       	if(tmp >= heap[child]) break;
        else{
        	heap[parent] = heap[child];
            parent = child;
            child *= 2;
        }
    }
    heap[parent] = temp;
    return item;
}

활용

• 운영체제의 작업 스케줄링
• Heap Sort (힙 정렬)
• 허프만 코딩
• 다익스트라 알고리즘: 선형 탐색을 이용하는 기존 방식에서 Min Heap을 이용하면 시간복잡도를 O(V^2)에서 O(ElogV)까지 줄일 수 있다. (V: 정점의 개수, E: 간선의 개수)

  다익스트라 알고리즘 (Dijkstra's Algorithm): 그래프의 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘

출처 및 참고

우선순위 큐 (Priority Queue)