📒 갈무리 - 우선순위 큐(Priority Queue)

📌 우선순위 큐란?

- 우선순위에 따라 정렬된 큐

- 어떠한 원소가 삽압되면 우선순위에 맞춰서 Queue가 정렬되고, 삭제는 정렬된 큐의 앞에서 이루어진다.

- Heap으로 구현되었기 떄문에 특정 원소를 삽입했을 때 생기는 정렬 과정은 O(logN)시간이다.

 

📌 우선순위 큐 메소드

push() : 원소 추가

pop() : top의 원소 제거

top() : 우선순위가 가장 높은 원소를 반환

empty() : 큐가 비어있으면 true 그렇지 않으면 false를 반환

size() : 큐의 원소의 개수를 반환

 

📌 직접 구현해 보자...

// C++

#include <iostream>
#include <queue>

using namespace std;

struct Student
{
	int id;
	int math;
	int eng;

	Student(int num, int math, int eng) : id(num), math(math), eng(eng) {}

	// < 연산자 오버로딩하여 우선순위 조정
	// id가 작은 것이 우선순위
	bool operator< (const Student s) const 
	{
		return this->id > s.id;
	}
};

int main()
{
	priority_queue<Student> pQueue;

	pQueue.push(Student(5, 80, 50));
	pQueue.push(Student(3, 60, 30));
	pQueue.push(Student(1, 50, 80));
	pQueue.push(Student(2, 65, 95));
	pQueue.push(Student(4, 70, 100));

	// 큐가 비어있지 않으면 실행
	while (!pQueue.empty())
	{
		// 우선순위가 가장 높은 데이터 반환
		// 데이터가 삭제되지는 않음
		Student student = pQueue.top();
		// 우선순위가 가장 높은 데이터 삭제
		pQueue.pop();
		cout << "우선순위가 가장 높은 데이터" << endl;
		cout << "학번 : "<<student.id << endl;
		cout << "math : "<<student.math << endl;
		cout << "eng : "<<student.eng << endl;
	}

	return 0;
}