[TIL / C++] 우선순위 큐와 힙

조재훈·2024년 8월 17일

개요

오늘 NHN 코딩 테스트를 진행했다. 문제 중에 못 푼 문제가 있는데 찾아보니 우선순위 큐를 사용하면 해결할 수 있다는 얘기가 있어서 우선순위 큐가 무엇인지는 알았는데 제대로 포스트로 다뤄보지 않은 것 같아 정리하려고 한다

우선순위 큐(Priority Queue)

우선순위 큐란?

우선순위 큐는 이름에서 알 수 있듯이 이미 알고있는 Queue와 유사하다. 데이터를 저장하고 뺄 수 있는 자료구조임

하지만 넣은 순서에 따라 pop되는 큐와는 다르게 우선순위 큐에 자료를 추가하면 데이터의 우선순위에 따라 정렬되어 사용자가 정한 우선순위대로 데이터를 꺼내쓸 수 있다

우선순위 큐는 뒤에서 이야기 할 힙으로 구현한다

사용

C++ STL에서는 기본적으로 우선순위 큐를 쓸 수 있도록 해준다. priority_queue<T>라는 타입을 제공해서 다음과 같이 선언할 수 있다

#include <queue>
...

int main()
{
	priority_queue<int> pq;
}

이렇게 선언하면 기본적으로 pq는 우선순위 큐가 되며 최댓값을 우선적으로 뽑아주는 큐가 된다.
그리고 데이터를 추가하고 제거해보면 높은 값부터 빼지는 걸 볼 수 있음

...
pq.push(3);
pq.push(7);
pq.push(10);

while(!pq.empty())
{
	cout << pq.top();
    pq.pop();
}
// 10 7 3

최댓값을 우선으로 하지 않고 최솟값이나 커스텀으로 지정하고 싶다면 변수를 선언할 때 지정해줘야 한다

int main() {
	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(3);
	pq.push(6);
	pq.push(10);

	while (!pq.empty())
	{
		cout << pq.top() << ' ';
		pq.pop();
	}
}

// 3 6 10

// 절댓값으로 커스텀 정렬
struct cmp
{
	bool operator()(int a, int b)
	{
		if (abs(a) > abs(b))
			return true;
		else if (abs(a) == abs(b))
		{
			if (a > b)
				return true;
			else
				return false;
		}
		
		return false;
	}
};

int main() {
	priority_queue<int, vector<int>, cmp> pq;
	pq.push(-3);
	pq.push(6);
	pq.push(-10);

	while (!pq.empty())
	{
		cout << pq.top() << ' ';
		pq.pop();
	}
}