개념

일반적인 Queue는 FIFO의 형태였다면 우선순위큐는 들어간 순서와 상관 없이 우선순위가 높은 데이터가 먼저 나오는 자료구조이다.

함수

enqueue() - 우선순위 큐에 원소 삽입
dequeue() - 우선순위가 가장 높은 원소 반환
peek() - queue에서 최대 우선순위 요소를 반환

구현

구현 방식에는 배열, 연결 리스트, 힙이 있다.

구현방법	enqueue()	dequeue()
배열	O(1)	O(N)
연결 리스트	O(1)	O(N)
정렬된 배열	O(N)	O(1)
정렬된 연결 리스트	O(N)	O(1)
힙	O(logN)	O(logN)

힙 방식이 삽입 삭제 모두 O(logN)을 보장하기 때문에 주로 힙으로 구현한다.