[C++] std::priority_queue 구조 알아 보기 | 우선순위 큐, 최대힙, 최소힙

개인적으로 공부하는 내용이므로 틀린 부분이 있을 수 있습니다. 있다면 알려주세요 :)

[std::priority_queue 란?]

std::priority_queue는 C++의 컨테이너 어댑터(container adapter) 중 하나이다. 컨테이너 어댑터란 vector와 같은 컨테이너의 일부 기능을 제한하여 만든 컨테이너를 말한다. 대표적으로 stack, queue, priority_queue가 있다. 컨테이너 어댑터의 특징으론 반복자를 지원하지 않는다. 따라서 범위 기반 for문에도 사용할 수 없다. std::priority_queue는 우선순위 큐라고도 불리는데, 내부적으로 힙(Heap)과 비슷하게 동작한다. 따라서 최대힙 또는 최소힙이 필요할 때 해당 컨테이너를 사용할 수 있다.

std::priority_queue는 <queue> 헤더에 정의되어 있으며 다음과 같은 템플릿 매개변수를 가진다.

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

T는 요소(element)의 타입을 의미하며, Container는 내부적으로 우선순위 큐 구현에 사용되는 컨테이너를 의미한다. 구현을 위해 front(), push_back(), pop_back() 을 지원하는 컨테이너가 필요한데 이를 만족하는 컨테이너는 vector와 deque(덱)이 있다고 한다. 따로 설정하지 않으면 default로 vector를 사용한다. Compare는 std::sort에서 사용되는 비교 함수와 비슷하다. 어떤 기준으로 우선순위를 정하여 저장할지 Compare로 설정한다. default는 less(a<b)로 되어 있으며 이는 최대힙을 의미한다. 즉 root 노드에 가장 큰 값이 온다. root에 가장 작은 값이 존재하는 최소힙을 원하면 미리 정의된 std::greater<>를 넣어주면 된다.

 

[컨테이너 생성 및 삽입 및 삭제 연산]

다음은 컨테이너를 생성하는 방법과 원소의 삽입 및 삭제를 보여준다.

#include <iostream>
#include <queue>

using namespace std;

void main()
{
    // default는 최대힙이다.
    priority_queue<int> maxHeap;
    
    // 원소 1,2,3,4,5를 삽입
    maxHeap.push(1); maxHeap.push(2);
    maxHeap.push(3); maxHeap.push(4);
    maxHeap.push(5);
    
    // 기본적으로 요소는 top(root)에만 접근 가능하다.
    // 최대힙이므로 top은 가장 큰 원소를 가진다.
    cout << maxHeap.top() << endl;  // 5;
    
    // 원소의 삭제는 pop으로 하며 top 원소가 삭제된다.
    maxHeap.pop();
    
    // 기존의 top인 5가 삭제되고, 그 다음으로 큰 4가 top이 된다.
    cout << maxHeap.top() << endl;  // 4;
    
    // 모든 요소를 차례대로 출력하고 싶을 땐 다음과 같이 작성한다.
    // 4 3 2 1
    while(!maxHeap.empty())
    {
    	cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
}

실행 결과)

 

 

다음은 기존의 벡터를 이용하여 우선순위 큐를 생성하는 예제이다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

void main()
{
	vector<int> v {3, 1, 5, 2, 6, 10};
    
	// v의 원소를 가진 컨테이너를 생성
	priority_queue<int, vector<int>, greater<int>> minHeap(v.begin(), v.end());
    
	// 1 2 3 5 6 10
	while (!minHeap.empty())
	{
		cout << minHeap.top() << " ";
		minHeap.pop();
	}
}

실행 결과)

 

 

[std::priority_queue의 모양 알아보기]

priority_queue는 인덱스 연산을 제공하지 않지만, 내부적으로 데이터를 저장하고 있는 vector는 인덱스 연산자를 제공한다. priority_queue는 이러한 내부적인 컨테이너를 protected 멤버 변수인  c에 저장하고 있다. 

 

따라서 priority_queue를 상속하여 c를 통해 데이터가 어떻게 저장되어 있는지 확인할 수 있다. 

class MyPriorityQueue : public priority_queue<int>
{
public:
	// 현재 컨테이너에 저장된 모든 요소를 인덱스 순으로 출력합니다.
	void PrintElements() 
	{
		for (size_t i = 0; i < c.size(); ++i)
		{
			cout << "[" << i << "]: " << c[i] << endl;
		}
		cout << "-----------------------------" << endl;
	}
};

void main()
{
	MyPriorityQueue maxHeap;
    
	// (1)
	maxHeap.push(1);
	maxHeap.push(2);
	maxHeap.PrintElements();
	
	// (2)
	maxHeap.push(3);
	maxHeap.PrintElements();
    
	// (3)
	maxHeap.push(9);
	maxHeap.PrintElements();
	
	// (4)
	maxHeap.push(8);
	maxHeap.PrintElements();

	// (5)
	maxHeap.pop();
	maxHeap.PrintElements();
}

 

위 연산 순서가 힙처럼 동작함을 확인하기 위해 다음과 같이 그림으로 나타내 보았다. 힙의 삽입 및 삭제 연산의 과정과 실제로 각 노드의 값을 저장하고 있는 벡터(배열)의 모습이다. 그리고 위의 PrintElements() 함수를 통해 출력된 결과와 비교하여 실제로 동일한지 확인할 것이다.

(1) push(1), push(2).  현재 가장 큰 수: 2(top)

(1)

(2) push(3). 현재 가장 큰 수: 3(top)

(2)

(3) push(9). 현재 가장 큰 수: 9(top)

(3)

(4) push(8). 현재 가장 큰 수: 9(top)

(4)

(5) pop(). 현재 가장 큰 수: 8(top)

(5)

 

아래는 실제 실행 결과이며 위 그림들의 각 벡터의 모습과 동일한 것을 확인할 수 있다.