Java
[Java] PriorityQueue(우선순위 큐)
Hyung1
2021. 1. 28. 17:36
728x90
반응형
FIFO구조의 일반적인 큐와는 다르게, 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) |
출처 :
728x90
반응형