📒Priority Queue

✍Priority Queue 이란?

Priority_queue 는 Queue의 한 종류로써, 우선순위에 따라 자동으로 정렬된 Queue다.
어떤 원소가 삽입된다면 주어진 우선 순위에 맞춰 Queue가 자동으로 정렬되고, 삭제 시에도 마찬가지로 자동으로 정렬된다.

✍특징

📌특징

• 기존의 Queue와 가장 큰 차이는 정렬이다.
• Heap 자료구조로 구현되었다.
• 특정 원소를 삽입해 생기는 정렬의 시간복잡도는 O(logN)이다.

📌헤더파일

#include < queue>

✍사용방법

📌생성

• priority_queue< 자료형, Container, 비교함수 > 변수명
  - 어떤 우선순위로 정렬할 지 비교함수 필요
  • Container는 보통 vector를 사용한다.(vector를 include하지 않아도 돌아간다.)
• priority_queue< 자료형 > 변수명
  - 내림차순(기본)으로 정렬하는 priority_queue

📌삽입, 삭제, 반환

• push() : Priority_queue에 원소 삽입(비교 함수에 따라 자동 정렬)
• pop() : 가장 앞의 원소를 삭제한다.
• top() : 가장 앞의 원소를 반환한다.(삭제되지 않음)

📌기타

• empty() : Priority_queue가 비어있는지 bool값을 반환.(비었다면 true, 아니라면 false)
• size() : Priority_queue의 크기를 반환한다.
• enqueue() : queue에 새 요소를 삽입한다.
• dequeue() : queue에 최대 우선 순위 요소를 삭제하고 그 값을 반환한다.
• peek() : queueu에서 최대 우선순위 요소를 반환한다.

queue와 다르게 front, back을 사용하지 않고 top을 사용한다.

기존의 Queue와 다르게 이미 정령이 되어있고, Queue의 특징을 모두 가지고 있기 때문에 삽입과 삭제가 자주 일어나지만 정렬이 필요한 문제에서 사용하면 유용하다.