4. Priority Queue & Heap

Priority Queue란?

Queue의 경우 먼저 들어간 데이터가 먼저 나오게 된다.

Priority Queue는 이와 다르게 들어간 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다.

 

그렇다면 Priority Queue를 어떻게 구현해야 할까?

 

첫번째, 배열로 구현하여 삽입 시마다 우선순위에 맞게 정렬한다.

이 방법은 항상 정렬된 형태를 유지하기 때문에 데이터를 꺼낼 때 용이하지만, 삽입 시 O(n)의 시간이 필요하다.

 

두번째, 리스트로 구현하여 데이터를 불러올 때 우선순위가 높은 데이터를 찾는다.

이 방법은 삽입 시 상수 시간이 걸려 용이하지만, 데이터를 꺼낼 때마다 O(n)의 시간이 필요하다.

 

이처럼 배열과 리스트로 Priority Queue를 구현하면 이와 같이 데이터 삽입이나 요청 시 시간이 걸린다는 단점이 있다.

그래서 주로 Priority Queue를 구현할 때 Heap이라는 자료구조를 사용하게 된다.

 

그렇다면 Heap이란 무엇이고, 사용하면 어떤 장점이 있는지 알아보자.

 

 

Heap이란?

Heap은 기본적으로 이진 트리의 형태로 데이터를 저장하는 자료구조이다.

가장 큰 특징은 데이터의 값에 따라 항상 정렬된 상태를 유지한다는 것이다.

이를 위해 Heap은 다음과 같은 규칙을 따른다.

 

 

① parent 노드의 우선순위 ≥ child 노드의 우선순위

 

항상 parent 노드가 child 노드보다 같거나 높은 우선순위를 갖는다.

 

이 때 큰 값이 높은 우선순위를 갖는 Heap을 Max Heap(최대 힙),

작은 값이 높은 우선순위를 갖는 Heap을 Min Heap(최소 힙) 이라고 한다.

 

따라서 root 노드가 항상 가장 높은 우선순위를 갖는다.

 

 

② Complete Binary Tree(완전 이진 트리)

 

Heap은 항상 완전 이진 트리 형태를 유지한다.

 

그렇다면 Heap을 통해 어떻게 Priority Queue를 구현하는지 알아보자.

 

 

Insertion

삽입은 항상 완전 이진 트리를 유지해야 하기 때문에 마지막 레벨의 가장 오른쪽에 삽입한다.

따라서 먼저 마지막 노드의 위치를 찾아야 한다.

 

 

위와 같은 Min Heap이 있다고 가정했을 때 12번 노드의 오른쪽에 새 노드가 삽입되어야 한다.

 

 

이제 해당 위치에 우선순위 1을 갖는 노드를 삽입해보자.

그러면 1번 노드가 parent 노드인 10번 노드보다 우선순위가 높아 규칙 ①에 맞지 않게 된다.

 

따라서 새로 삽입한 노드를 우선순위에 맞는 위치로 옮겨야 할 필요가 있다.

새로 삽입한 노드의 우선순위가 더 높기 때문에 parent 노드와 위치를 바꾸어가며 적합한 위치를 찾게 된다.

이렇게 새로 삽입한 노드의 우선순위를 맞추기 위해 parent 노드와 바꾸는 작업을 UpHeap이라고 한다.

UpHeap 작업은 parent 노드의 우선순위가 더 높을때까지 반복한다.

 

 

먼저 삽입한 위치의 parent인 10번 노드와 UpHeap을 통해 위치를 바꿔준다.

하지만 아직도 parent 노드보다 우선순위가 높기 때문에 또 UpHeap을 해야 한다.

 

 

 

이렇게 추가적으로 UpHeap을 2번 더 수행하여 완전 이진 트리 형태와 정렬 상태를 만족하게 되었다.

 

따라서 삽입 과정에 걸리는 최대 시간은 트리의 높이에 비례하여 O(h)가 된다.

또한 Heap은 항상 완전 이진 트리 형태를 유지하기 때문에 h는 logN에 비례하므로 O(logN)이라고도 할 수 있다.

 

 

Removal

앞서 말했듯 Heap에서 가장 우선순위가 높은 노드는 root 노드이다.

따라서 가장 우선순위가 높은 노드를 뽑으려면 root 노드를 뽑으면 된다.

 

하지만 이렇게 root 노드를 없애게 되면 해당 위치가 비게 되므로 바로 없앨 수는 없다.

이 때문에 Heap에서는 먼저 root 노드를 가장 마지막 노드와 바꾸고 뽑게 된다.

 

 

예를 들어 위와 같은 Min Heap에서 가장 우선순위가 높은 노드를 뽑아보자.

가장 우선순위가 높은 노드는 root 노드인 1번 노드이다.

 

 

앞서 설명한대로 먼저 제거할 노드인 1번 노드와 마지막 노드인 10번 노드를 바꿔준다.

 

 

이제 1번 노드를 제거해도 완전 이진 트리의 형태가 유지되게 된다.

하지만 마지막 노드인 10번 노드가 root 노드의 위치에 있어 child 노드보다 우선순위가 낮은 문제가 생긴다.

이 때문에 해당 노드를 child와 바꾸며 적절한 위치까지 내려가게 되는데 이를 DownHeap이라고 한다.

DownHeap 작업은 모든 child 노드의 우선순위가 해당 노드보다 낮을 때까지 반복한다.

 

※ DownHeap 시 left child와 right child 모두 우선순위가 높을 때는 둘 중 우선순위가 낮은 child와 바꾼다.

(MinHeap의 경우 숫자가 큰 노드가 우선순위가 낮으므로 두 child 중 숫자가 큰 노드와 바꿈)

우선순위가 더 낮은 노드와 바꾸어야 DownHeap 횟수가 작아질 가능성이 높기 때문이다.

 

 

 

두 child 노드가 모두 우선순위가 낮을 때까지 2번 DownHeap을 실행해주었다.

이렇게 완전 이진 트리 형태와 우선순위 정렬 상태를 유지할 수 있다.

 

따라서 삭제도 노드를 제거하는데는 상수 시간이 걸리지만 DownHeap에 O(h)의 시간이 소요된다.

마찬가지로 h는 logN에 비례하므로 O(logN)이라고도 할 수 있다.