[자료구조] 우선순위 큐(PriorityQueue) + 힙(Heap) - 2

프로그래머스 프린터라는 문제를 풀다가 의아한 점이 생겼다.

PriorityQueue priority = new PriorityQueue<>(Collections.reverseOrder());

우선순위 큐를 사용하기 위해 우선순위 큐를 생성하고, 문제에서 숫자가 클 수록 우선순위가 높다고 요구하여 내림차순으로 설정을 했다.

그런데 우선순위 큐에 {2,5,4,1,3}을 넣었을 때 내가 단순히 생각하기에는 {5,4,3,2,1}이 나올 것이라고 생각했지만,

실제로는 {5,3,4,1,2}가 나왔다.

???

자바 공식 문서에서도

reverseOrder()
Returns a comparator that imposes the reverse of the natural ordering.

라고 했다. 내림차순이라는 소리다.

알고보니, 우선순위 큐가 힙으로 구현되어 있기 때문이었다.

 

{5,4,3,2,1}의 형태로 안나오는것이 당연하다..!!

최대 힙을 그려보면 {5,3,4,1,2} 의 모양으로 완전 이진트리가 생성된다.

 

여기서 주의해야 할 점은 우리가 Sysout의 형태로 출력했을 때는 {5,3,4,1,2}가 출력되지만, 실제로 동작은 {5,4,3,2,1}로 동작한다.

??? : 이게 뭔 dog소리야

라고 할 수 있지만, 이는 최대 힙에서의 데이터 삭제 과정을 한 번 슉 보고 오신다면 바로 이해가 될것이다.

간단하게, 5가 pop 되는 순간 제일 아래의 2가 루트 노드로 올라오게 되고 다시 최대 힙을 찾기 위한 재정렬이 발생하기 때문에 실제 동작은 {5,4,3,2,1}로 동작하는 것이다!!!!!

 

ReverseOrder를 사용하지 않고, Comparator를 이용해 직접 정의를 할 수도 있다.

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(5, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

 

큐와 우선순위 큐는 다르다.

우선순위 큐

핵심연산

• enqueue : 데이터 삽입

• dequeue : 데이터 삭제

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.

구현방법

1. 배열 기반

2. 연결 리스트 기반

3. 힙 기반

보통 삽입의 위치를 찾기 위해 첫 번째 노드에서부터 시작해 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

그래서 우선순위 큐는 단순배열과 연결 리스트가 아닌 '힙'을 사용해 구현하는 것이 일반적이다.

힙의 특징

힙은 이진 트리인데 '완전 이진 트리'이다. 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

즉, 루트 노드에 저장된 값이 가장 커야 한다.

최대 힙(max heap) : 루트 노드로 올라 갈 수록 저장된 값이 커지는 완전 이진 트리

최소 힙(min heap) : 루트 노드로 올라 갈 수록 저장된 값이 작아지는 완전 이진 트리

enqueue

새로운 데이터를 삽입할 때, `우선순위가 제일 낮다는 가정하에 완전 이진 트리를 만족하는 가장 마지막 위치에 저장`한다.

그리고 부모 노드와 우선순위를 비교해 바뀌어야 한다면 바꿔준다(루트 노드와 비교할 때 까지)

dequeue

루트 노드의 자리에 있는 값이 삭제되면, 제일 마지막에 들어간 원소를 루트 노드로 올린다.

(제일 마지막 원소는 가장 아래 level의 오른쪽 원소이다.)

그 후 루트노드의 원소와 서브 트리의 원소 값과 비교해서 최소,최대 힙에 맞게 자리를 교환해준다.

연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 `마지막 위치`에 추가하기가 쉽지 않아 배열을 기반으로 구현한다.

노드의 고유 번호

• 루트 노드의 인덱스가 1일 때

부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2

왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2

오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2 + 1

• 루트 노드의 인덱스가 0일 때

부모 노드의 인덱스 값 : (자식노드의 인덱스-1) / 2

왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2 + 1

오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2 + 2