우선 순위 큐

우선순위 큐(Priority queue)란?

FIFO가 아니라 우선 순위가 높은 데이터가 먼저 나오는 큐이다.

• 모든 데이터에 우선순위가 있다.
• dequeue할때, 우선순위가 높은 순서대로 나간다.
• 우선순위가 같은 경우에는 FIFO순서대로 나간다.

우선순위 큐 - Enqueue, Dequeue

• 우선순위 큐를 heap으로 구현한 경우, 최소 힙 및 최대 힙의 삽입/삭제와 같다.
  

우선순위 큐 구현

• 우선 순위 큐는 배열, 연결리스트, 힙으로 구현할 수 있다.
• 자바 내부에 구현되어 있는 우선순위 큐는 힙으로 구현 되어있다.

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

(정렬되지 않은 경우에는 enqueue와 dequeue의 시간 복잡도가 서로 바뀜)