우선순위 큐 HEAP ||C++ STL priority queue

1. 힙(Heap)

 

(1) 완전 이진트리

(2) 모든 노드에 저장된 값(우선순위)들은 자식 노드들의 것보다 (우선순위가) 크거나 같다.

※ 직접 연결된 자식-부모 노드 간의 크기만 비교하면 됩니다.

 

=> max Heap 이냐 min Heap이냐에 따라 맨 위에 위치하는 노드의 값이 가장 크거나 작습니다.

max Heap / min Heap 예시 

 

 

2. 우선순위 큐 (Priority Queue)

 

max Heap과 min Heap의 경우 C++의 queue 헤더를 이용하여 코드상 구현할 수 있습니다. 

 

(1) queue 헤더를 선언해줍니다.

#include <queue>

 

(2) 변수를 선언해줍니다. 선언하는 방법이 다소 어려우니 외워두면 좋습니다. 

priority_queue<int> pq; // max Heap default
priority_queue<int, vector<int>, less<int>> pq;  //max Heap
priority_queue<int, vector<int>, greater<int>> pq; //min Heap

 

(3) 코드 사용 예제

int main()
{
    
    
    priority_queue<int, vector<int>, less<int>> maxpq;  //max Heap
    priority_queue<int, vector<int>, greater<int>> minpq; //min Heap
    
    maxpq.push(1);maxpq.push(2);maxpq.push(3);
    
    minpq.push(1);minpq.push(2);minpq.push(3);
    
    cout << "최대힙 ";
    while(!maxpq.empty())
    {
        cout << maxpq.top() <<" ";
        maxpq.pop();
    }
    
    cout << '\n'<<"최소힙 ";
    while(!minpq.empty())
    {
        cout << minpq.top() <<" ";
        minpq.pop();
    }
    
    return 0;
}

 

실행화면

 

 

* 오늘은 최대 힙, 최소 힙이라는 자료구조와 C++에서 이를 어떻게 사용하는지 (priority queue)에 대해 정리해보았습니다. 다음에는 좀 더 세세한 예제로 정리해보아야겠습니다.