[Java] PriorityQueue(우선순위 큐)

 FIFO구조의 일반적인 큐와는 다르게, PriorityQueue(우선순위)는 들어온 순서와 상관없이 데이터를 꺼낼 때 우선순위가 가장 높은 데이터가 가장 먼저 나온다. 

 

PriorityQueue의 내부구조

AbstractQueue를 상속하고 Serializable를 확장하고 있다.

 

 oracle docs의 문서를 살펴보았을때 PriorityQueue의 특징을 살펴보면,

• 내부구조가 heap으로 되어있다.
• null 값을 허용하지 않는다.
• 비교 불가능한 객체의 삽입도 허용하지 않는다,  (실행하면 ClassCastException이 Throw 된다.)
• PriorityQueue 클래스와 그 반복자는  Collection 및 iterator 인터페이스의 메서드의 모든 것을 구현한다. 하지만 iterator() 메서드로 순회했을 때 순서를 보장하지 않는다. 순서를 지정할 필요가 있는 경우 Arrays.sort(pq.toArray()) 사용을 고려한다.
• Thread-safe 하지 않다. 몇개의 thread가 리스트의 구조를 변경하는 경우는 복수의 thread가 PriorityQueue 인스턴스에 동시에 접속해서는 안된다. 대신에 thread-safe인 PriorityBlockingQueue 클래스 사용을 고려해본다.

PriorityQueue의 용량

기본 초기 용량은 11이다.

private static final int DEFAULT_INITIAL_CAPACITY = 11;

용량이 초과하면 자동으로 용량을 늘려준다.

• 기존 용량이 64보다 작으면 기존용량 + 기존용량 + 2로 늘려준다. 즉, 거의 2배로 늘려준다.
• 기존 용량이 64보다 크면 원래 용량 + 원래 용량 / 2로 늘려준다. 즉, 1.5배로 늘려준다.

힙(Heap)의 시간 복잡도

Priority Queue의 내부 구조는 heap으로 되어있기에 heap의 시간복잡도를 봐보자.

 

oracle docs의 내용중..

Implementation note: this implementation provides O(log(n)) time for the enqueuing and dequeuing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size)

 

add(), offer()	remove()	remove(Object), contains()	peek(), size()
O(logN)	O(logN)	O(n)	O(1)

 

출처 : 

widrbs96 / Today-I-Learn

docs.oracle.com/javase/8/docs/api/