[자료구조] - 우선순위 큐(Priority Queue)

 

 

 

 

 

 

우선순위 큐 (Priority Queue)

우선순위 큐는 기존 큐와 달리 가장 먼저 들어온 원소가 가장 먼저 제거되지 않습니다.

우선순위 큐에서는 우선순위가 가장 높은 원소부터 제거됩니다.

 

 

 

 

 

 

 

 

 

우선순위 큐의 구현

우선순위 큐는 다양한 방법으로 구현이 가능합니다.

구현 방법	삽입	최댓값 삭제	최솟값 삭제	임의원소 삭제(찾은 후)	검색
정렬되지 않은 ArrayList	$$O(1)$$	$$O(n)$$	$$O(n)$$	$$O(n)$$	$$O(n)$$
정렬되지 않은 LinkedList	$$O(1)$$	$$O(n)$$	$$O(n)$$	$$O(1)$$	$$O(n)$$
정렬된 ArrayList (오름차순)	$$O(n)$$	$$O(1)$$	$$O(n)$$	$$O(n)$$	$$O(log\;n)$$
정렬된 LinkedList (내림차순)	$$O(n)$$	$$O(1)$$	$$O(n)$$	$$O(1)$$	$$O(n)$$
이진검색트리 (BST)	$$O(log\;n)$$	$$O(log\;n)$$	$$O(log\;n)$$	$$O(log\;n)$$	$$O(log\;n)$$
최대 힙 (Max Heap)	$$O(log\;n)$$	$$O(log\;n)$$	$$O(n)$$	$$O(log\;n)$$	$$O(n)$$

 

 

 

우선순위 큐는 대부분의 경우 최대 힙(Max Heap)을 사용하여 구현합니다.

우선순위 큐의 삽입과 삭제가 다른 자료구조에 비해 평균적으로 빠르기 때문입니다.

 

 

 

 

 

이진검색트리 대신 힙을 사용하는 이유

이진검색트리는 완전 이진트리가 아니므로 배열로 구현할 경우 메모리 낭비가 심할 수 있습니다.

따라서 연결 체인으로 구현하며, 이는 같은 시간복잡도를 가지더라도 배열로 구현한 Max Heap보다 오랜 시간이 걸립니다.

 

 

 

 

 

 

 

 

 

우선순위 큐와 힙의 차이점

 

앞서 살펴보았듯이 힙은 우선순위 큐를 구현하기 위한 하나의 수단일 뿐, 힙이 아니더라도 우선순위 큐를 구현할 수 있습니다.

 

 

즉 다음과 같습니다.

우선순위 큐는 힙으로 구현될 수 있다 - O
힙은 우선순위 큐로 구현될 수 있다 - X

우선순위 큐는 힙이다 - X
힙은 우선순위 큐이다 - X

힙은 그 자체로 우선순위 큐로 사용될 수 있다 - O

 

 

 

 

 

 

 

 

 

 

 

자바로 구현

최대 힙을 그 자체로 우선순위 큐로 쓸 수 있습니다.

따라서 최대 힙의 구현방법을 올려두겠습니다.

https://ttl-blog.tistory.com/709

[Java] 자바로 Heap 구현하기

 

 

 

참고 - Heap이란?

https://ttl-blog.tistory.com/708

[자료구조] - 힙(Heap)