자료구조[10] Priority Queue

Priority Queue

개요

우리가 어떤일을 함에 있어 우선 순위라는 것이 존재한다.
예를 들어 CPU에서 프로그램 실행에서 매우 중요한 A라는 일과 카톡 메시지를 처리하는 B라는 일이 있다고 해보자.
우선 순위는 당연히 A가 높아야하고 A를 먼저 처리해주어야 한다.

그렇기 때문에 우리는 우선 순위가 제일 높은 task를 찾아서 그것을 먼저 처리해야한다.
이때 사용하는 것이 heap 자료구조이다. 만약 그냥 array를 이용해서 우선 순위를 찾으려면 시간 복잡도는 O(N)이 될 것이다.
그래서 heap을 사용해 O(1)로 우선 순위를 찾을 수 있도록 구현한다.

Get (remove) a Largest value

Logical Level

우선 순위 task를 처리했다면 이를 지워줘야한다. 이때 Heap의 특성이 유지 되도록 지워야한다.

1. 맨 아래 오른쪽 끝에 있는 노드 값을 root 노드 값에 copy한다.
2. 맨 아래 오른쪽 끝에 있는 노드를 delete한다.
3. heap 특성을 유지하기 위해 Reheapdown 과정을 거친다.

위의 heap에서 우선 순위 처리 작업을 한다 해보자.

우선 task를 처리한 후 맨 아래 오른쪽 끝에있는 노드 값을 copy해준다.

그 후 노드를 delete한다.

그리고 heap 특성을 유지하기 위해 reheapDown을 한다.

위의 상황에선 둘 중에 더 큰쪽과 바꾼다. (위에선 40)

전부 바꾼 후엔 위처럼 만들어진다.

Implementation Level

reheapDown을 구현해보자.

template<class ItemType>
void HeapType<ItemType>::reheapDown(int root, int bottom_id){
	int maxChild;
    int leftChild = root*2 + 1;
    int rightChild = root*2 + 2;
    
    if (leftChild <= bottom_id){
    	if (leftChild == bottom_id){
        	maxChild = leftChild;
        }
        else {
        	if (items[leftChild] <= items[rightChild]){
            	maxChild = rightChild;
            }
            else {
            	maxChild = leftChild;
            }
        }
        if (items[root] < items[maxChild]){
        	swap(items[root], items[MaxChild]);
            reheapDown(MaxChild, bottom_id);
        }
    }
}

구현

template<class Itemtype>
class PQType {
private:
	heapType<ItemType> heap; // heap 이용
    int length;
    int max_items;
public:
	PQType();
    ~PQType():
    PQType(const PQType<ItemType> &);
    void operator=(const PQType<ItemType> &);
    void enqueue(ItemType item);
    void dequeue(ItemType& item);
    void clear();
    bool isFull() const;
    bool isEmpty() const;
};

template<class ItemType>
sturct HeapType {
	ItemType* items;
    int num_items;
    
    void reheapUp(int root, int bottom_id);
    void reheapDown(int root, int bottom_id);
};

template<class ItemType>
PQType<ItemType>::PQType(int max) {
	max_items = max;
    heap.items = new ItemType(max) // 동적할당
    length = 0;
}

template<class ItemType> // 소멸자
PQT<ItemType>::~PQType(int max) {
	delete[] heap.items;
}

template<class ItemType>
void PQType<ItemType>::clear() {
	length = 0;
}

template<class ItemType>
void PQT<ItemType>::enqueue(ItemType item) {
	if (length == max_items) {
    	return;
    }
    heap.items[length] = item;
    heap.reheapUp(0, length);
    length++;
}

template<class ItemType>
void PQT<ItemType>::dequeue(ItemType item) {
	if (length == 0) {
    	return;
    }
    item = heap.items[0];
    heap.items[0] = heap.items[length - 1];
    heap.reheapDown(0, length);
    length--;
}

enqueue와 dequeue 모두 최대 tree의 높이 만큼 reheap이 일어난다.
complete tree이기 때문에 높이는 $log(N)$이고 시간복잡도도 $O(log(N))$이 된다.

시간복잡도

priority queue를 heap과 sorted list, BST로 구현했을 때 시간복잡도를 비교해보자.