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

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

단순 리스트를 이용하여 구현할 수 있고, 또는 힙(heap)을 이용하여 구현할 수 있다.

 

힙(Heap)은 완전 이진 트리 자료구조의 일종으로, 항상 루트노드를 제거한다.

완전 이진 트리: 루트 노드부터 시작하여 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 트리

힙은 최소힙과 최대힙으로 나뉜다.

최소힙 : 루트 노드가 가장 작은 값을 가지므로, 값이 작은 데이터가 우선적으로 제거된다.

최대힙 : 루트 노드가 가장 큰 값을 가지므로, 값이 큰 데이터가 우선적으로 제거된다.

 

---

아래는 Cpp 클래스로 직접 우선순위 큐를 사용해 본 예제이다.

 

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

using namespace std;

struct MyCompare
{
	bool operator() (string s1, string s2)
	{
		return s1.length() > s2.length();
	}
};

int main()
{
	// 우선순위 큐는 Default 가 내림차순
	priority_queue<int> pq;

	pq.push(30);
	pq.push(10);
	pq.push(20);

	while(!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	// 결과: 30 20 10
	cout << endl;

	///////////////////////////////////////////////////////////////////////////

	/* 오름차순 정렬 방법 */
	// 우선순위 큐는 힙을 이용한 트리구조 이므로 실제로 데이터를 저장할 공간 vector<int> 가 필요하다.
	priority_queue<int, vector<int>, greater<int>> pq2;

	pq2.push(30);
	pq2.push(10);
	pq2.push(20);

	while (!pq2.empty())
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}
	// 결과: 10 20 30
	cout << endl;

	///////////////////////////////////////////////////////////////////////////

	priority_queue<string, vector<string>> pq3;

	pq3.push("C");
	pq3.push("B");
	pq3.push("A");

	while (!pq3.empty())
	{
		cout << pq3.top() << " ";
		pq3.pop();
	}
	// 결과: C B A
	cout << endl;

	///////////////////////////////////////////////////////////////////////////

	priority_queue<string, vector<string>, MyCompare> pq4;

	pq4.push("Hello");
	pq4.push("c++");
	pq4.push("world~");

	while (!pq4.empty())
	{
		cout << pq4.top() << " ";
		pq4.pop();
	}
	// 결과: C B A
	cout << endl;
}

---

참조영상

https://www.youtube.com/watch?v=dUjd2BYU6zg&t=209s 

https://www.youtube.com/watch?v=AjFlp951nz0