[자료구조] 우선 순위 큐(Priority Queue)

우선 순위 큐

우선 순위를 가진 항목들을 저장하는 큐

FIFO 순서가 아닌 우선 순위에 따라서 순서가 결정된다.

 

ADT

객체

n개의 element 형의 우선 순위를 가진 요소들의 모임

 

연산

• push(data) : 우선 순위 큐에 데이터를 추가한다. (시간 복잡도 : O(log2n))
• pop() : 우선 순위 큐에서 가장 우선순위가 높은 요소를 삭제한다.  (시간 복잡도 : O(log2n))
• empty() : 우선 순위 큐가 비었는지 확인한다.
• size() : 우선 순위 큐의 크기를 구한다.
• top() : 우선 순위 큐에서 가장 우선순위가 높은 요소를 반환한다.

 

#include <iostream>
#include <vector>

typedef int element;
using namespace std;

class priorityQueue{
    private:
        vector<element> heap;
        int heap_size;
    public:
        priorityQueue(){
            heap_size = 0;
        }
        
        bool empty(){
            if(heap_size)return false;
            else return true;
        }

        int size(){
            return heap_size;
        }
        element top(){
            return heap[1];
        }

        void push(element data){
            int parent, child;
        
            parent = (heap_size - 1) / 2;
            child = heap_size;
            heap.push_back(data);
            while(child > 0 && heap[parent] < heap[child]){
                element tmp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = tmp;

                child = parent;
                parent = (child - 1) / 2;
            }
            ++heap_size;
        }

        void pop(){
            if(empty())return;
            int parent, child;
            heap[0] = heap[--heap_size];

            parent = 0; 
            child = 1;

            while(child <= heap_size){
                if(child < heap_size && heap[child] < heap[child+1])child++;

                if(heap[parent] >= heap[child])break;
                else{
                    element tmp = heap[parent];
                    heap[parent] = heap[child];
                    heap[child] = tmp;
                }
                parent = child;
                child = parent * 2 + 1;
            }
        }
        void print(){
            cout << "[";
            for(int i = 0; i < heap_size; i++)cout << heap[i] << " ";
            cout << "]\n";
        }
};

int main(){
    priorityQueue* heap = new priorityQueue();
    
    heap->push(10);
    heap->print();

    heap->push(20);
    heap->print();

    heap->push(50);
    heap->print();

    heap->push(30);
    heap->print();

    heap->push(40);
    heap->print();

    heap->push(0);
    heap->print();


    heap->pop();
    heap->print();

    heap->pop();
    heap->print();
    /*
	[8 ]
	[19 8 ]
	[23 8 19 ]
	[32 23 19 8 ]
	[45 32 19 8 23 ]
	[56 32 45 8 23 19 ]
	[45 32 19 8 23 ]
	[32 23 19 8 ]	    
    */
}