[JAVA] PriorityQueue 란?

필자는 코딩테스트를 볼 때 우선순위를 구해야 할 때 굉장히 손쉽게 구할 수 있다는 장점이 있어서 자주 사용하였다.

하지만 "어떻게 동작하는지 설명 해주실 수 있나요?" 라는 질문에 머리를 한대 맞은 느낌이었다.

내가 원리를 제대로 알고 사용하지 않았구나 하고 반성을 했으며 공부 해보았다.

PriorityQueue란?

우선 순위 힙을 기반으로하는 제한되지 않은 우선 순위 큐이다.

출처 : docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

우선순위 큐란 들어가는 순서에 상관없이 우선순위가 높은순서대로 나오는 큐를 뜻한다.

PriorityQueue (Java Platform SE 7 )

그렇다면 힙은 무엇일까 ?

Heap 이란?

• 힙은 완전이진트리입니다.
• 대소관계는 오로지 부모와 자식간의 비교로만 이루어진다.

출처 :  ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

 

예제

 

 

삽입

• 제일 하위에 추가한다.
• 부모와 비교한 후 자신이 우선순위가 높다면 위치를 바꾼다.
• 자신이 우선순위가 낮거나 root일 때까지 2번을 반복한다.

삭제

• root 를 제거한다.
• 제일 하위에 있는 원소를 root로 이동한다.
• 자식중 자신보다 우선순위가 높은 원소가 있다면 위치를 바꾼다.
• 우선순위가 자신보다 높은게 없거나 리프노드일때까지 3번을 반복한다.

그렇다면 왜 우선순위 큐는 힙을 이용하여 구현을 할까 ?

시간복잡도에서 heap이 우위를 가지기에 heap으로 구현이 되어있다.