[자료구조]#7_우선순위 큐

 

[자료구조]#7_우선순위 큐

 

우선순위 큐 자료구조에 대해 알아보겠습니다.

 

---

 

Overview

 

1. 개념
2. 구현
3. 참고

 

#0. 개념

1. 우선순위 큐

• 정의 : 우선순위 큐(Priority Queue)는 원소들이 우선순위에 따라 정렬된 연결 자료구조로, 원소의 삽입 순서와 무관하게 가장 높은 우선순위를 가진 원소가 먼저 나오는 특징을 갖고 있습니다. 우선순위 큐는 원소 간 우선순위를 유지하기 위해 삽입/삭제 수행 시 정렬 작업을 자동적으로 수행합니다. 따라서, 우선순위 큐 자료구조는 내부적으로 항상 정렬된 상태를 유지합니다.
• 성능 : 우선 순위 큐의 삽입/삭제 작업의 평균/최악 시간 복잡도는 O(log n)입니다. 일반적으로, 우선순위 큐는 "힙(heap)" 자료구조를 통해 구현하며, 삽입/삭제 작업은 최대 힙 혹은 최소 힙의 정렬 작업에 걸리는 시간을 의미합니다. 
• 활용처 : 우선순위 큐는 대기열 관리, 작업 스케줄링 관리, 그리고 최단 경로 탐색 등 우선순위에 따라 작업을 처리할 때 사용하기 용이합니다.
• 단점 : 우선순위 큐는 내부적으로 정렬된 상태를 유지하기 위해, 삽입/삭제 작업 수행 시 매번 정렬 작업을 수행합니다. 이때, 정렬 작업을 수행하기 위해 추가적인 메모리 공간이 필요하며, 그 구현이 비교적 복잡합니다.

 

#1. 구현

1. 최소 힙(이진 힙)

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

class PriorityQueue
{
private:
	vector<int> heap;

public:
	PriorityQueue(){}

public:
	int parent(int i)
	{
		return (i - 1) / 2;
	}

	int left(int i)
	{
		return i * 2 + 1;
	}

	int right(int i)
	{
		return i * 2 + 2;
	}

	int getSmallerIndex(int i, int j)
	{
		if (heap[i] < heap[j])
			return i;
		else
			return j;
	}

	bool IsEmpty()
	{
		return heap.empty();
	}

public:
	void push(int val)
	{
		heap.push_back(val);
		int Idx = heap.size() - 1;

		while (Idx > 0 && heap[parent(Idx)] > heap[Idx])
		{
			swap(heap[parent(Idx)], heap[Idx]);
			Idx = parent(Idx);
		}
	}

	int pop()
	{
		if (heap.empty())
			return -1;

		int root = heap[0];
		heap[0] = heap.back();	
		heap.pop_back();

		int Idx = 0;
		while (left(Idx) < heap.size())
		{
			int smallerIdx = getSmallerIndex(left(Idx), right(Idx));
			if (heap[Idx] < heap[smallerIdx])
			{
				swap(heap[Idx], heap[smallerIdx]);
				Idx = smallerIdx;
			}
			else
			{
				break;
			}
		}

		return root;
	}

};

int main()
{
	PriorityQueue pq;

	pq.push(3);
	pq.push(10);
	pq.push(6);
	pq.push(2);
	pq.push(8);

	cout << "Popped elements: ";
	while (!pq.IsEmpty()) {
		cout << pq.pop() << " ";
	}
	cout << endl;

	return 0;
}

 

Details

 

[자료구조]#5_트리

 

• 우선 순위 큐를 구현하는 대표적인 방법은 "최소 힙"을 활용하는 방법입니다.
• 힙은 반 정렬 상태를 유지하는 완전 이진트리의 한 종류입니다. 자세한 내용은 위 링크를 살펴보세요.

 

#2. 참고

1. priority_queue 컨테이너

[Basic C++] #69_priority_queue

 

2. BOJ_1966번 문제, 우선순위 큐 활용 문제

[BOJ알고리즘, C++]#1966_프린터 큐, 우선순위 큐, 큐