[Java] PriorityQueue와 Queue의 차이

이전에 작성했던 Queue 관련 글

bmangrok.tistory.com/entry/Queue-%ED%81%90

 

 

PriorityQueue와 Queue는 이름만 비슷할 뿐 그 쓰임새는 매우 다르다.

원소를 꺼낼 때 Queue는 철저하게 FIFO을 따르지만 PriorityQueue는 정해진 우선 순위에 따라 원소를 출력한다.

우선 순위는 사용자가 특정해줄 수 있고, 특정해주지 않는다면 오름차순으로 출력된다.

즉, PriorityQueue<Integer>를 poll() 하는경우 가장 낮은 숫자가 나온다.

 

이 사실을 모르고 Queue를 계속 쓰다가 원하는 결과가 안나와서 한참 씨름했다.

 

인자로 넣어줄 리스트 몇 개를 확인해보니 오름차순으로 정렬되어 있길래, 다른 리스트도 전부 오름차순인 줄 알았는데, 오름차순이 아닌게 있었다.

그냥 PriorityQueue를 썼으면 해결됐을 문제.

 

PriorityQueue는 이진 트리 구조를 따르며, 원소가 추가되거나 출력될 때마다 이진트리 비교를 실행하여 가장 낮은 원소를 맨 앞으로 대기시킨다.

따라서 PriorityQueue<Integer>의 맨 앞 원소를 출력하면 언제나 가장 낮은 숫자가 출력된다.

 

이진트리