[Java] PriorityQueue(우선순위큐)를 알아보자.

created:2013-01-03

updated:2016-08-10

edit

일반적인 큐(Queue)는 선입선출(FIFO)의 구조를 가진다는 것은 다들 아시고 있을 것이라고 생각된다. 그렇다면 PriorityQueue 는 일반적인 큐와 어떻게 다를까?

PriorityQueue는 내부적으로 Natural Ordering 에 따라서 정렬하는 큐이다. 그래서 다음의 코드를 테스트 해보면 당연히 10이라는 숫자가 나와야 하는데, 실제로는 1이라는 숫자가 나오는 것을 확인 할수 있다.

또 다른 예를 보자. 아래와 같이 무작위로 숫자 값을 넣었을 경우에는 어떻게 될까?

ASC Ordering 된 상태로 출력되는것을 확인 할수 있을것이다. 이것이 가장 큰PriorityQueue의 특징이다. PriorityQueue는 널을 허용하지 않는다. 왜냐하면 PriorityQueue는 기반 자체가 natural ordering에 기초하고 있기 때문에 정렬할수 없는 null은 허용되지가 않는다.

PriorityQueue의 head는 가장 적은 값이 온다. 만약 다수의 엘리먼트가 가장 적은값이라면, 헤드는 그 중에 하나가 되는데 어떤것이 될지는 모른다.

메소드들

함수	기능	element 삭제유무	비어있는 경우
peek	head를 가져옴.	X	return null
poll	head를 가져옴.	O	return null
remove	head를 가져옴.	X	throw exception
element	head를 가져옴.	O	throw exception

계산 복잡도

함수	계산복잡도
offer, poll, remove, add	O(log(n))
remove(obj), contains(obj)	linear time
peek, element	constant time

그러나, iterator를 사용시에는 주의해야 한다. PriorityQueue는 기본적으로 natural ordering 이 되는데, iterator() 함수를 이용해서 Iterator를 생성했을 때에는 그것이 보장되지 않는다. 다음의 코드를 실행시켜 보자.

앞에서 말한대로라면 for문을 이용해서 poll() 함수로 element들을 빼 왔을때에는 정렬된 채로 나왔었기 때문에 Iterator를 이용할때에도 같은 결과가 나와야 하는데, while 문을 이용해서 출력해보면 정렬된 결과가 나오지 않는 것을 확인할 수가 있다. 필자가 실행 시켰을 경우에는 다음과 같은 결과가 나왔다.