우선순위 큐 (Priority Queue)

이번에는 우선순위 큐(Priority Queue)에 대해서 알아보자.

 

우선순위 큐는 큐에서 요소들에게 우선순위가 부여되며 우선순위가 높은 요소가 먼저 출력되는 큐이다.

(en.wikipedia.org/wiki/Priority_queue)

 

여기서 요소란 무엇을 의미할까?

 

요소는 일반적으로 우선순위를 결정짓는 키(key)와 그 키와 매핑이 되는 값(value)으로 구성된다.

 

요소의 키는 일반적으로 정수를 사용하며 키 값의 대소 관계로 요소들의 우선순위를 결정짓는다.

 

요소의 값은 애플리케이션에서 실제로 사용하는 데이터이며 정수, 실수, 문자열 등의 데이터 타입이 될 수 있으며

 

여러 가지 데이터 타입들로 구성된 복합 데이터 타입(composite data type)이 될 수 있다.

(en.wikipedia.org/wiki/Composite_data_type)

 

여기서 우리가 알아보고자 하는 것은 큐에서 요소의 키 값의 대소 관계로 어떻게 우선순위를 결정짓는가이다.

 

따라서 우리는 요소의 키 값을 중점적으로 볼 것이며 값(value) 자체는 다루지 않을 것이다.

 

그리고 키 값이 큰 값일수록 더 높은 우선순위를 갖도록 최대 힙(max heap)을 사용하여 설명할 것이다.

 

힙(heap)이란 완전 이진트리를 기반으로 하는 자료구조로 최댓값 또는 최솟값을 빠르게 찾기 위해 힙 속성을 갖고 있다.

 

우리가 사용할 힙은 최대 힙이고 최대 힙 속성은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크다는 것이다.

 

즉, 우선순위 큐를 구현하기 위해 요소들의 키 값들 중에서 최댓값을 빠르게 찾기 위해 최대 힙을 사용한다는 것이다.

 

최대 힙을 완전 이진트리로 나타낸다는데 구체적으로 어떻게 나타낼까?

 

먼저 완전 이진트리를 설명하자면 자식 노드를 최대 2개까지 가질 수 있는 트리가 이진트리이고

 

이진트리의 마지막 레벨을 제외한 다른 레벨들은 노드들로 가득 차있고

 

마지막 레벨은 왼쪽부터 오른쪽 방향으로 노드들이 채워져 있어야 완전 이진트리가 된다.

(en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees에서 complete binary tree 참고)

 

이 완전 이진트리를 기반으로 한 최대 힙을 보통 배열로 나타내는데 아래 그림을 보면 이해하기 쉬울 것이다.

 

 

위 그림은 최대 힙을 나타낸 것으로 노드 위에 있는 값은 배열의 인덱스를 나타내고 노드 안에 있는 값은 요소의 키 값을 나타낸다.

 

트리에 있는 키 값들이 위에서부터 왼쪽에서 오른쪽으로 차례대로 배열에 저장되어 있다.

 

트리가 최대 힙 속성을 만족하고 있는지 확인해 보자.

 

어느 노드든 그 노드의 키 값이 항상 자식 노드의 키 값보다 크거나 같음을 확인할 수 있다.

 

이러한 최대 힙 속성을 만족시키게 하는 HeapifyUpward 함수와 HeapifyDownward 함수 두 개를 정의해 보자.

 

typedef int Element;
class MaxHeap
{
protected:
    std::vector<Element> _elements;
    
    void exchange(std::size_t idx1, std::size_t idx2)
    {
        Element temp = _elements[idx1];
        _elements[idx1] = _elements[idx2];
        _elements[idx2] = temp;
    }
    
    std::size_t parent(std::size_t idx)
    {
    	if(0 < idx)
        {
        	return (idx - 1) / 2;
        }
        return 0;
    }
    
public:
    void HeapifyDownward(std::size_t idx, std::size_t size)
    {
        std::size_t largest = idx;
        std::size_t left = idx * 2 + 1;
        std::size_t right = (idx + 1) * 2;
        
        if (size > left && _elements[idx] < _elements[left])
        {
            largest = left;
        }
        if (size > right && _elements[largest] < _elements[right])
        {
            largest = right;
        }
        if (idx != largest)
        {
            exchange(idx, largest);
            HeapifyDownward(largest, size);
        }
    }
    
    void HeapifyUpward(std::size_t idx)
    {
    	std::size_t pidx = parent(idx);
        while(1 <= idx && _elements[pidx] < _elements[idx])
        {
            exchange(idx, pidx);
            idx = pidx;
            pidx = parent(idx);
        }
    }
};
            

 

HeapifyDownward 함수는 idx에 있는 노드의 키 값을 자식 노드들 중에서 더 큰 키 값을 갖고 있다면 교환한다.

 

키 값을 교환했다면 함수명대로 트리의 아래 방향으로 진행하며 트리 전체가 최대 힙 속성을 만족시키도록 재귀적으로 호출된다.

 

HeapifyUpward 함수는 idx에 있는 노드의 키 값이 부모 노드의 키 값보다 크다면 키 값을 교환한다.

 

키 값을 교환한다면 트리의 윗 방향으로 진행하며 트리 전체가 최대 힙 속성을 만족시키도록 한다.

 

다음으로 우선순위 큐인 힙에 요소를 추가하거나 추출하는 Insert 함수와 Extract 함수 두 개를 정의해 보자.

 

typedef int Element;
class MaxHeap
{
protected:
    std::vector<Element> _elements;
    
    void exchange(std::size_t idx1, std::size_t idx2)
    {
        ...
    }
    
    std::size_t parent(std::size_t idx)
    {
    	...
    }
    
public:
    void HeapifyDownward(std::size_t idx, std::size_t size)
    {
        ...
    }
    
    void HeapifyUpward(std::size_t idx)
    {
    	...
    }
    
    void Insert(Element element)
    {
        _elements.push_back(element);
        HeapifyUpward(_elements.size() - 1);
    }
    
    bool Extract(Element& element)
    {
        const std::size_t size = _elements.size();
        if(1 > size)
        {
            return false;
        }
        
        element = _elements[0];
        exchange(0, size - 1);
        _elements.pop_back();
        HeapifyDownward(0, size - 1);
        return true;
    }
};
            

 

Insert 함수는 힙의 가장 마지막에 요소를 넣고 최대 힙 속성을 만족시키게 하기 위해서 HeapifyUpward 함수를 호출한다.

 

Extract 함수는 힙의 루트 노드를 추출하고 힙의 마지막 요소를 루트 노드로 대체한 후

 

최대 힙 속성을 만족시키도록 HeapifyDownward 함수를 호출한다.

 

이제 시간 복잡도를 계산해 보자.

 

우선순위 큐의 시간 복잡도를 결정하는 함수는 HeapifyUpward 함수와 HeapifyDownward 함수이다.

 

HeapifyUpward 함수는 리프 노드에서 루트 노드까지 반복할 때가 최악의 경우이고

 

HeapifyDownward 함수는 루트 노드에서 리프 노드까지 재귀호출될 때가 최악의 경우이다.

 

힙에 요소가 총 n개 있다면 완전 이진트리의 높이는 $\log_{2}n$이므로 시간 복잡도는 $O(\log_{2}n)$이 되겠다.

 

여기까지 우선순위 큐에 대해 알아보았다.

 

내용 출처 : Introduction to Algorithms (en.wikipedia.org/wiki/Introduction_to_Algorithms)