[queue] Priority Queue

Priority Queue

 

• 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것
• 일반적인 큐(Queue)는 First in-First Out (어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나감) 구조이다.  
• priority queue는 모든 연산을 O(log n)에 지원하는 binary heap으로 구현
  • insert : element 추가
  • find : priority가 가장 높은 element 반환
  • delete : priority가 가장 높은 element 제거
  • top : priority가 가장 높은 element를 반환
  • pop : priority가 가장 높은 element를 제거

 

 

# priority가 높다

 

• priority가 integer일때
  • C++은 가장 큰 숫자(max-heap based) 기준
  • Java의 경우 가장 작은 숫자(min-heap based) 기준

example)

priority_queue<int> q;
q.push(3);
q.push(5);
q.push(7);
q.push(2);
cout<<q.top(); // 7
q.pop();
cout<<q.top(); // 5
q.pop();
q.push(6);
cout<<q.top(); // 6
q.pop();