우선순위 큐와 힙의 차이

 

큐(Queue): 먼저 들어오는 데이터가 먼저 나가는 구조 (FIFO - First In First Out)

 

우선순위 큐(Priority Queue): 우선순위가 높은 데이터가 먼저 나가는 구조

 

힙(Heap): 루트 노드에 가장 큰 값 혹은 가장 작은 값을 저장하고 있는 완전이진트리

 

 

 

여기서, 우선순위 큐는 일반적으로 힙을 통해 구현한다.

 

배열, 연결리스트 등으로 구현할 수도 있지만,

 

최악의 경우 우선순위를 찾기 위해 인덱스의 끝까지 탐색할 수 있기 때문이다.

 

반면에 힙은 부모 노드, 자식 노드와의 비교만으로 노드의 자리를 찾기 때문에 시간 복잡도가 낫다.

- 새 데이터 삽입: O(log2n)

- 데이터 삭제: O(log2n)

 

 

 

둘을 비슷하거나 같게 보는 경우가 있는데, 엄연히 말하면 다르다.

 

추상화하면 우선순위 큐는 우선순위에 따라 일차원적으로 정렬된 큐 형태로 생각되어진다.

 

반대로 힙은 이러한 큐의 값을 꺼낼 때마다 우선순위에 따라 정렬되어 나와지도록 돕는 이진 트리 형태이기 때문이다.

 

힙이 큐가 인큐(Enqueue), 디큐(dequeue)를 할 때 보조하는 역할이라고 보면 좋을 듯하다.

 

 

---

 

 

왜 다른지 확실히 그 흥미로운 차이점을 Java 코드로 체감해보자.

 

우선 코드에 대한 조건 3가지가 있다.

 

조건 1) pq의 자료형은 Integer이다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

 

조건 2) 주어지는 입력은 5 4 2 7 6 11 3 8 8로 정렬이 되지 않은 수이다.

 

조건 3) pq는 들어오는(인큐되는) Integer의 값을 기준으로 오름차순 정렬하는 우선순위 큐 객체이다.

(pq에 위의 입력이 들어가면 논리적으로 2 3 4 5 6 7 8 8 11가 나올 것이라 기대한다.)

 

 

 

아래의 두 코드는 pq의 길이만큼 반복을 하여 우선순위 값인 int 값을 반환한다.

 

그럼 여기서 질문, 두 결과 값은 같을까 다를까? 곰곰이 생각해보자.

 

for(int i : pq){
    System.out.println(i);
}

 

while (!pq.isEmpty()){
    System.out.println(pq.poll());
}

 

 

 

 

.

.

.

.

.

.

.

 

 

 

 

결론부터 말하자면 다르다!

 

첫번째 코드는 2 5 3 7 6 11 4 8 8을 결과로 뿌린다.

 

두번째 코드는 2 3 4 5 6 7 8 8 11을 결과로 뿌린다.

 

눈치가 빠르다면 알아차렸다시피

 

첫번째 코드는 트리로 정렬된 순서대로 접근해서 저런 결과를 보여주는 것이고, 

 

두번째 코드는 큐의 방식으로 순서대로 접근했기 때문에 저런 결과를 보여주는 것이다.

 

우리가 기대하는 결과는 당연히 두번째이다.

 

 

 

 

 

마지막으로 참고할 만한 세번째 코드를 살펴보자.

int lth = pq.size();
for(int i=0; i<lth; ++i){
    System.out.println(pq.poll());
}

 

( 자바의 일반적이지 않은 디큐 방식이다. lth를 뽑은 이유는 디큐를 할수록 요소의 수가 줄어들기 때문이다. 줄어들 때마다 새로운 pq의 크기인 pq.size()를 호출해 for문에서 비교하면 치명적인 오류가 발생한다. )

 

자바에서 우선순위 큐를 다룰 때 이 점들을 꼭 유의하자.

 

 

 

결론적으로 우리는 두번째 방식인 아래 코드를 pq의 일반적인 디큐 방식으로 사용한다.

while (!pq.isEmpty()){
    System.out.println(pq.poll());
}

 

 

 

위의 결과는 마찬가지로 2 3 4 5 6 7 8 8 11를 출력한다.

 

두번째와 세번째 코드의 결과가 같은 이유는,

 

PriorityQueue의 poll() 메서드는 Queue의 방식으로 노드들을 반환하기 때문이다.

 

( https://www.geeksforgeeks.org/priorityqueue-poll-method-in-java/ )

PriorityQueue poll() Method in Java - GeeksforGeeks