Priority Queue

Max priority queue: root의 값이 가장 크고 자식의 값은 부모보다 작거나 같은 Tree

Min priority queue: root의 값이 가장 작고 자식의 값은 부모 보다 크거나 같은 Tree

empty(), size(), insert(), top(), delete()등의 기능이 있음

empty(), size(), top()은 O(1), insert()와 delete()는 O(logn)

Binary 형태의 Priority queue는 Heap Sort에 사용됨 (Average, best, worst O(nlogn)

Job Scheduling Problem에서 LPT algorithm 에 사용됨 (Max priority queue로 가장 긴 일을 골라 Min priority queue로 가장 일하고 있는 시간이 짧은 machine를 골라 할당함. 일이 n개 , 기계가 m개일때 O(nlog(mn)))

 

BInary Tree이면 Max heap이나 Min heap이 되며 배열로 구현하는게 가장 효과적. Heap의 높이는 log(n+1)

C++ STL에는  Priotrioty Queue라는 이름으로 있으며 vector로 element를 저장. 기본값은 max heap