[자료구조/C,C++]우선순위 큐 사용하기

Goal

우선순위 큐 구조
우선순위 큐 사용 예제
*시간복잡도

우선순위 큐 구조

priority_queue <T, Container, Compare> pq
priority_queue <int, vector, less> pq //큰 값부터 반환
priority_queue <int, vector, greater> pq //작은 값부터 반환

T : 자료형, 구조체 및 클래스
Container : vector와 같은 컨테이너
Compare : 우선순위를 결정하는 클래스

priority_queue 함수

q.push(value) : 삽입
q.pop() : 삭제
q.top() : minHeap의 경우 가장 작은 값, maxHeap의 경우 가장 큰 값을 리턴
q.size() : queue의 크기
q.empty() : queue에 한개이상 들어있으면 false, 아무것도 없으면 true를 리턴

우선순위 큐 사용 예제

소스코드

#include <iostream>
#include <queue>
#include <string>
using namespace std;

//Person 구조체
struct Person{
  string name;
  int age;
};

//두 Person중 크기가 작은것을 반환
struct cmp{
  bool operator()(Person a, Person b){
      return a.age<b.age;
  }
};

int main(){
  priority_queue<Person, vector<Person>, cmp> pq;
  
  Person person[4];
  person[0] = {"철수", 20};
  person[1] = {"영희", 23};
  person[2] = {"형주", 25};
  person[3] = {"주형", 52};
  
  for(int i = 0 ; i<4 ; i++)
      pq.push(person[i]);
  
  for(int i = 0 ; i<4 ; i++){
      Person tmp = pq.top();
      cout << tmp.name <<' '<<tmp.age<<'\n';
      pq.pop();
  }
  return 0;
}

결과

주형 52
형주 25
영희 23
철수 20
Program ended with exit code: 0

시간복잡도

삽입, 삭제 : O(logn)