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

우선순위 큐를 이래하기 위해선 먼전 heap을 알아야한다.

https://codinghago.tistory.com/97

[자료구조] 힙(heap) 최소힙(min heap), 최대힙(max heap) C++ 구현

 

📍 우선순위 큐(Priority Queue)란? 

Queue는 먼저 들어오는 데이터가 먼저 나가는 선입선출(FIFO)형식의 자료구조이다. 

Priority Queue는 Queue에 우선순위 개념을 도입한 자료구조로 들어오는 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나간다.  

 

• 큐(Queue) : 먼저 들어오는 데이터가 먼저 나가는 선입선출(FIFO) 구조
• 우선순위 큐(Priority Queue) : 우선순위가 높은 데이터가 먼저 나가는 구조
• 힙(Heap) : 루트 노드에 최대값이나 최소값을 저장하고 있는 완전이진트리

우선순위 큐는 heap자료구조로 구현된다. 그래서 우선순위 큐의 삽입, 삭제 연산또한 O(logN) 시간복잡도를 가진다. 

데이터 셋이 지속적으로 변하는 상황에서 우선순위에 따라 처리하고 싶을 때와 모든 키를 정렬할 필요가 없는 알고리즘 구현할 때 유용하다. 

 

1️⃣ 우선순위 큐(Priority Queue)의 구현

 

우선순위 큐는 일반적으로 힙을 사용해서 구현한다. 

힙은 일반적으로 배열을 이용하여 구현한다. 

완전 이진트리이므로 중간에 비어있는 요소가 없기 때문이다. 

 

위 그림과 같이 트리의 각 노드에 번호를 붙이고, 이 번호를 배열의 인덱스로 생각하면 이해하기 쉽다. 

배열로 구현을 하면 힙과 같은 이유로 부모 또는 자식 노드를 찾아가는 연산을 구현하기 쉽다. 

• 루트 노드 : 
  • 배열의 인덱스 1번부터 시작
  • 루트노드는 항상 인덱스 1에 위치
• 부모와 자식 간의 관계 : 
  • 왼쪽 자식 : (부모의 인덱스) * 2 위치에 저장
  • 오른쪽 자식  : (부모의 인덱스) * 2 + 1 위치에 저장
  • 부모 노드 : (자식의 인덱스) / 2 -- 정수 나눗셈  위치에 저장

 

✅ 우선순위 큐를 힙이 아닌 배열로 또는 연결리스트를 이용해서 구현할 수도 있다. 

하지만 배열과 연결리스트는 선형 구조의 자료구조이므로 삽입 또는 삭제 연산을 위한 시간복잡도는 O(n)이다. 

반면 힙트리는 완전 이진트리 구조기 때문에 힙트리의 높이는 log₂(n+1) 이며, 힙의 시간복잡도는 O(log₂n)이다. 

 

아래의 표를 보면 힙으로 구현한 것이 시간복잡도가 제일 적은 알 수 있다. 

구현방법	삽입	삭제
순서없는 배열	O(1)	O(n)
순서없는 연결리스트	O(1)	O(n)
정렬된 배열	O(n)	O(1)
정렬된 연결리스트	O(n)	O(1)
힙	O(log₂n)	O(log₂n)

 

✅ 우선순위 큐의 주요 연산자

• insert(x) : 우선순위 큐에 요소 X추가
• remove() : 우선순위 큐에서 가장 우선순위가 높은 요소를 삭제하고 반환
• find() : 우선순위 큐에서 가장 우선순위가 높은 요소를 반환

 

2️⃣ 우선순위 큐(Priority Queue) C++로 구현하기

1). 노드 구조체 

template <typename T>
struct Node{
    private : 
        int key; // 우선순위 
        T data;  
    public : 
        Node(){
            key = 0;
        }    
        Node(int _key, T _data){
            key = _key;
            data = _data;
        }

        ~Node(){}

        // getter/ setter
        int getKey(){
            return key;
        }
        void setKey(int _key){
            key = _key;
        }
        T getData(){
            return data;
        }
        void setData(T _data){
            data = _data;
        }
};

 

2).  노드 탐색 함수

// search node
        Node<T>& getParent(int index){
            return node[index/2] ;
        }
        Node<T>& getLeftChild(int index){
            return node[index*2] ;
        }
        Node<T>& getRightChild(int index){
            return node[index*2+1] ;
        }

 

3).  삽입 

// 삽입
        void insert(int key, T data){
            if(isFull()){
                cout << "Heap is Full" <<endl;
                return;
            }
            
            int index = ++size; // 힙트리 마지막 노드의 다음 위치에서 시작

            // 힙트리를 거슬러 올라가며 부모 노드와 우선순위 비교 
            while(index != 1 && key > getParent(index).getKey()){
                node[index] = getParent(index);
                index /= 2;
            }

            // 최종 위치에 데이터 삽입
            node[index].setKey(key);
            node[index].setData(data);
        }

 

4).  삭제

// 삭제
        T remove(){
            if(isEmpty()){
                cout << "Heap is Empty" << endl;
                exit(EXIT_FAILURE);
            }

            Node<T> itemNode = node[1]; // 루트 노드(삭제 대상)
            Node<T> lastNode = node[size--]; // 힙트리의 마지막 노트 
            int index = 1; // 루트 노드 부터 시작

            //루트 노드부터 내려가며 자식 노드와 비교
            while(index <= size){
                if(index*2 > size){ // 자식 노드가 없는 경우
                    break;
                }else if(index*2 == size){ // 자식 노드가 하나인 경우
                    if(lastNode.getKey() < getLeftChild(index).getKey()){
                        node[index] = getLeftChild(index);
                        index *=2;
                    }
                }else{ // 자식 노드가 두개인 경우 
                    int leftChildKey = getLeftChild(index).getKey();
                    int rightChildKey = getRightChild(index).getKey();

                    // 둘 중 key가 더 큰 자식노드와 교환
                    if(lastNode.getKey() < leftChildKey || lastNode.getKey() < rightChildKey){
                        node[index] = leftChildKey > rightChildKey ? getLeftChild(index) : getRightChild(index) ;
                        index = leftChildKey > rightChildKey ? index*2 : index*2=1;
                    }else{
                        break;
                    }
                }
            }
            node[index] = lastNode; // 마지막 노드를 최종 위치에 저장
            return itemNode.getData(); // 삭제  노드의 data 반환
        }

 

5).  main함수 

int main (){
    MaxHeap<int> priorityQueue;

    // 삽입 
    priorityQueue.insert(10,10);
    priorityQueue.insert(5,5);
    priorityQueue.insert(30,30);
    priorityQueue.insert(8,8);
    priorityQueue.display();

    // 삭제
    priorityQueue.remove();
    priorityQueue.display();
}

 

6). 전체 코드 

#include <iostream>
using namespace std;

#define MAX_ELEMENT 200; 

template <typename T>
struct Node{
    private : 
        int key; // 우선순위 
        T data;  
    public : 
        Node(){
            key = 0;
        }    
        Node(int _key, T _data){
            key = _key;
            data = _data;
        }

        ~Node(){}

        // getter/ setter
        int getKey(){
            return key;
        }
        void setKey(int _key){
            key = _key;
        }
        T getData(){
            return data;
        }
        void setData(T _data){
            data = _data;
        }
};

template <typename T>
class MaxHeap{
    private : 
        Node<T> node[MAX_ELEMENT];
        int size; // heap의 데이터 갯수
    public : 
        MaxHeap(){
            size = 0 ;
        }
        ~MaxHeap(){}

        // search node
        Node<T>& getParent(int index){
            return node[index/2] ;
        }
        Node<T>& getLeftChild(int index){
            return node[index*2] ;
        }
        Node<T>& getRightChild(int index){
            return node[index*2+1] ;
        }

        // 삽입
        void insert(int key, T data){
            if(isFull()){
                cout << "Heap is Full" <<endl;
                return;
            }
            
            int index = ++size; // 힙트리 마지막 노드의 다음 위치에서 시작

            // 힙트리를 거슬러 올라가며 부모 노드와 우선순위 비교 
            while(index != 1 && key > getParent(index).getKey()){
                node[index] = getParent(index);
                index /= 2;
            }

            // 최종 위치에 데이터 삽입
            node[index].setKey(key);
            node[index].setData(data);
        }

        // 삭제
        T remove(){
            if(isEmpty()){
                cout << "Heap is Empty" << endl;
                exit(EXIT_FAILURE);
            }

            Node<T> itemNode = node[1]; // 루트 노드(삭제 대상)
            Node<T> lastNode = node[size--]; // 힙트리의 마지막 노트 
            int index = 1; // 루트 노드 부터 시작

            //루트 노드부터 내려가며 자식 노드와 비교
            while(index <= size){
                if(index*2 > size){ // 자식 노드가 없는 경우
                    break;
                }else if(index*2 == size){ // 자식 노드가 하나인 경우
                    if(lastNode.getKey() < getLeftChild(index).getKey()){
                        node[index] = getLeftChild(index);
                        index *=2;
                    }
                }else{ // 자식 노드가 두개인 경우 
                    int leftChildKey = getLeftChild(index).getKey();
                    int rightChildKey = getRightChild(index).getKey();

                    // 둘 중 key가 더 큰 자식노드와 교환
                    if(lastNode.getKey() < leftChildKey || lastNode.getKey() < rightChildKey){
                        node[index] = leftChildKey > rightChildKey ? getLeftChild(index) : getRightChild(index) ;
                        index = leftChildKey > rightChildKey ? index*2 : index*2=1;
                    }else{
                        break;
                    }
                }
            }
            node[index] = lastNode; // 마지막 노드를 최종 위치에 저장
            return itemNode.getData(); // 삭제  노드의 data 반환
        }

        // 출력 
        void display(){
            int level = 1;
            for(int i = 1; i<= size; i++){
                if(i==level){
                    cout << endl;
                    level *=2; 
                }
                count << node[i].getData() << "(" << node[i].getKey() << ")";
            }
            cout << '\n' << "----------------------------------" << endl;
        }

        bool isEmpty(){
            return size == 0;
        }
        boo isFull(){
            return size == MAX_ELEMENT -1 ; 
        }
        
};

int main (){
    MaxHeap<int> priorityQueue;

    // 삽입 
    priorityQueue.insert(10,10);
    priorityQueue.insert(5,5);
    priorityQueue.insert(30,30);
    priorityQueue.insert(8,8);
    priorityQueue.display();

    // 삭제
    priorityQueue.remove();
    priorityQueue.display();
}

코드 출처 : https://suyeon96.tistory.com/31#---%--C%-B%-B%EC%--%--%EC%--%-C%EC%-D%--%--%EC%-A%B-%EC%--%A-%EC%--%-C%EC%-C%--%--%ED%--%--%--%EC%--%AC%EC%-A%A-%---STL-

 

 

이번 코드는 정말 C++의 객체 지향적인 스타일을 잘 담은 코드인것 같다. 

이해하는데 정말정말 어려웠지만 그래도 한번 보고 나니까 조금 수월해졌다. 

우선순위 큐코드를 보면서 계속 했갈렸던게 Node개념인데 그냥 내가 직접 정의 하는 자료구조라고 생각하면 편한것 같다. 

 

7) C++  priority_queue 라이브러리 

#include <iostream>
#include <queue>
using namespace std;

int main(){
    // maxheap
    priority_queue<int, vector<int>, less<int>> pq1;
    pq1.push(5);
    pq1.push(2);
    pq1.push(3);
    pq1.push(10);

    cout << "Max Heap PQ : ";
    while(!pq1.empty()){
        cout << pq1.top() << " ";
        pq1.pop();
    }
    cout << endl;

    // minheap
    priority_queue<int, vector<int>, greater<int>> pq2;
    pq2.push(1);
    pq2.push(11);
    pq2.push(15);
    pq2.push(6);
    pq2.push(3);

    cout << "Min Heap PQ : " ;
    while(!pq2.empty()){
        cout << pq2.top() << " ";
        pq2.pop();
    }
    cout << endl;
}

 

 

---

참고 자료 

https://suyeon96.tistory.com/31#---%--C%-B%-B%EC%--%--%EC%--%-C%EC%-D%--%--%EC%-A%B-%EC%--%A-%EC%--%-C%EC%-C%--%--%ED%--%--%--%EC%--%AC%EC%-A%A-%---STL-

 

https://velog.io/@yun8565/%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90-Priority-Queue

우선순위 큐 (Priority Queue)

https://chanhuiseok.github.io/posts/ds-4/

자료구조 - 우선순위 큐(Priority Queue)와 힙(heap)

https://velog.io/@signkite/Java-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queue

https://kghworks.tistory.com/196

[algorithm] 정렬 3. 우선순위 큐 (Priority Queues)

https://be-senior-developer.tistory.com/25

[최소 힙] c++ 구현 및 설명