PriorityQueue — 우선순위 힙 기반 큐
PriorityQueue — 우선순위 힙 기반 큐
PriorityQueue<E>는 우선순위 힙(priority heap)을 기반으로 하는 무한(unbounded) 우선순위 큐예요. 요소는 사용된 생성자에 따라 자연 순서(natural ordering) 또는 큐 생성 시 제공된 Comparator에 따라 정렬돼요. null 요소는 허용되지 않아요.
본문
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable
자연 순서에 의존하는 우선순위 큐는 비교 불가능한 객체의 삽입도 허용하지 않아요(ClassCastException 발생 가능). 큐의 머리(head)는 지정된 순서 기준에서 가장 작은 요소예요. 여러 요소가 최소로 동률이면 그중 하나가 머리가 되며 동률은 임의로 깨져요. poll, remove, peek, element 같은 검색 연산은 머리 요소에 접근해요.
큐는 무한하지만 내부 용량이 배열 크기를 관리해요. 요소가 추가되면 용량이 자동으로 커져요. iterator()와 spliterator()는 어떤 특정 순서로 요소를 순회한다는 보장이 없어요. 정렬된 순회가 필요하면 Arrays.sort(pq.toArray())를 사용해요.
이 구현은 동기화되지 않아요. 여러 스레드가 하나의 스레드라도 큐를 수정한다면 동시에 접근하면 안 돼요. 대신 스레드 안전한 PriorityBlockingQueue를 사용해요.
성능: 큐에 넣고 빼는 연산(offer, poll, remove(), add)은 O(log n), remove(Object)/contains(Object)는 선형, 검색 연산(peek, element, size)은 상수 시간이에요. Java Collections Framework의 멤버예요.
생성자
PriorityQueue()— 기본 초기 용량(11)으로 자연 순서에 따라 정렬해요.PriorityQueue(int initialCapacity)— 지정 초기 용량, 자연 순서로 만들어요.PriorityQueue(Comparator)— 지정 비교자로 정렬해요.PriorityQueue(int, Comparator)— 지정 초기 용량과 비교자로 만들어요.PriorityQueue(Collection)/PriorityQueue(PriorityQueue)/PriorityQueue(SortedSet)— 지정 컬렉션의 요소를 담아 만들어요.
메서드
add(E)/offer(E)— 요소를 큐에 삽입해요.peek()— 머리를 제거하지 않고 반환해요.poll()— 머리를 제거하고 반환해요.remove(Object)— 요소 하나를 제거해요.contains(Object)/clear()/size()— 기본 컬렉션 연산이에요.toArray()/toArray(T[])— 큐를 배열로 변환해요(순서 없음).iterator()— 특정 순서 없이 순회하는 반복자를 반환해요.comparator()— 요소를 정렬하는 비교자를 반환하고, 자연 순서면null을 반환해요.spliterator()— late-binding·fail-fast이며SIZED,SUBSIZED,NONNULL특성을 보고하는 충분절자를 만들어요(ORDERED아님).removeIf/removeAll/retainAll/forEach— 컬렉션 기본 연산들이에요.