[Chapter16] - 힙으로 우선순위 유지하기 #23
Description
이진 트리와 이진 힙
이진 힙 ⊂ 완전 이진 트리 ⊂ 이진 트리 구조로 포함 관계가 성립한다.
이진 트리(Binary Tree)
이진 트리란, 각 노드가 최대 두 개의 자식(왼쪽, 오른쪽)을 가진 트리를 의미한다.
graph TD
A[10]
A --> B[5]
A --> C[20]
B --> D[3]
B --> E
C --> F[15]
C --> G[30]
이진 힙(Binary Heap)
이진 힙은, 이진 트리 중에서도 완전 이진 트리 구조를 가지면서, 힙 속성을 만족하는 형태를 의미한다.
graph TD
A[1]
A --> B[3]
A --> C[6]
B --> D[5]
B --> E[9]
C --> F[8]
위와 같이, 왼쪽부터 차례대로 채워지고, 부모의 값이 자식 보다 작아야한다는 힙 속성이 있다.
힙 속성
힙은 값을 검색하기에 전혀 좋지 않은 자료구조이다.
graph TD
A[100]
A --> B[88]
A --> C[25]
B --> D[87]
B --> E[16]
C --> F[8]
C --> G[12]
D --> H[86]
D --> I[50]
E --> J[2]
E --> K[15]
F --> L[3]
최대 힙에서는 루트 노드가 항상 최대값을 가지지만, 그렇다고 힙의 맨 마지막 노드(last node)가 항상 최소값을 가지고 있다는 보장이 없다. 여기서 마지막 노드는 3을 의미한다.
그렇기에, 최소값인 2는 캐싱을 할 수 있겠지만, 3과 같은 애매한 수를 찾는다면, 탐색이 어려울 것이다. 따라서, 힙은 이진 탐색 트리에 비해 약한 정렬(weakly ordered)라고 말한다.
힙의 구현
책에서 설명된 힙은 기본적으로 트리 구조를 가지고 있다. 때문에 특정 값을 넣으려면, 마지막 노드를 찾아 그 오른편에 값을 넣어야 한다.
예시로, 위 힙 속성에서 본 트리 구조에서 40을 넣는다고 가정해보자. 40을 넣기 위해서는, 마지막 노드의 부모인 8의 오른쪽 노드를 넣어야 완전 이진 트리가 되지만, 8보다 큰 값이기에 넣을 수 없다. 때문에, 스왑하여 자신의 위치를 찾도록 해야한다.
- 우선 8의 오른쪽 노드에 40을 넣는다.
- 8과 위치를 바꾼다.
- 25와 위치를 바꾼다.
graph TD
A[100]
A --> B[88]
A --> C[40]
B --> D[87]
B --> E[16]
C --> F[25]
C --> G[12]
D --> H[86]
D --> I[50]
E --> J[2]
E --> K[15]
F --> L[3]
F --> M[8]
따라서 위와 같은 트리 구조가 될 것이다.
하지만 삽입을 하기 위해서 마지막 노드를 찾아야 하는데, 어떻게 찾아야할까? 트리 구조에서 가장 쉬운 방법은 마지막 노드를 찾기 위해 BFS을 사용하는 것이다. 하지만 이는, O(N)이 걸린다. 대용량 데이터의 경우 처리 속도가 많이 늦어지게 된다.
이처럼 트리 구조에서 마지막 노드를 빠르게 찾는 것은 쉽지 않기 때문에, 힙은 주로 배열로 구현한다. 배열로 표현하면 마지막 노드는 단순히 인덱스 size - 1에 존재하므로 O(1)에 접근할 수 있다.
[100, 88, 40, 87, 16, 25, 12, 86, 50, 2, 15, 3, 8]
100,
88, 40,
87, 16, 25, 12,
86, 50, 2, 15, 3, 8
이렇게 배열로 표현하면, 마지막 노드도 빠르게 찾을 수 있고, 수학 계산을 통해 특정 위치에 있는 노드를 빠르게 찾을 수 있다.
| 노드 | 인덱스 관계 | 설명 |
|---|---|---|
| 왼쪽 자식 | 2 * i + 1 | i번째 노드의 왼쪽 자식 인덱스 |
| 오른쪽 자식 | 2 * i + 2 | i번째 노드의 오른쪽 자식 인덱스 |
| 부모 노드 | (i - 1) / 2 (정수 나눗셈) | i번째 노드의 부모 인덱스 |
이렇게 찾는게 가능한 이유는 바로 완전 이진 트리 구조를 가지기 때문이다. 이를 통해, 삽입을 위해 마지막 노드를 찾는 것은 O(1)이 걸리게 되고, 삽입 후 힙 속성을 복구하는 과정(Heapify Up)까지 포함하여 시간 복잡도를 O(logN)으로 줄일 수 있게 된다.
우선순위 큐
자바의 우선순위 큐(PriorityQueue) 구현을 살펴보자.
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
transient Object[] queue;
...
}앞에서 정리한 내용과 같이 queue는 Object[]로 구현이 되어있다.
그렇다면, 코틀린에서 PriorityQueue를 사용할 때 삽입을 호출하면 어떤 일이 발생하는지 보자.
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x, queue, comparator);
else
siftUpComparable(k, x, queue);
}PriorityQueue는 항상 힙(Heap) 구조를 기반으로 동작하지만, Comparator를 지정하느냐에 따라 정렬 기준(우선순위)이 달라진다.
Comparator가 지정되지 않으면, 내부에서는 Comparable.compareTo()를 사용해 오름차순으로 정렬한다. 이때 루트가 가장 작은 값이 되므로 PriorityQueue는 최소 힙(Min-Heap) 형태로 동작한다.
private static <T> void siftUpUsingComparator(
int k, T x, Object[] es, Comparator<? super T> cmp) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (cmp.compare(x, (T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = x;
}
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = es[parent];
if (key.compareTo((T) e) >= 0)
break;
es[k] = e;
k = parent;
}
es[k] = key;
} - k는 현재 삽입된 노드의 인덱스 (맨 마지막 위치).
(k - 1) >>> 1→ 부모 인덱스를 계산.- 오른쪽 쉬프트는
(k - 1) / 2와 동일 (정수 나눗셈).
- 오른쪽 쉬프트는
- 부모보다 값이 크거나 같으면 중단 (break).
- 즉, 최소 힙에서 부모 ≤ 자식이므로 더 이상 올라갈 필요 없음.
- 부모보다 작다면 부모를 아래로 내리고(
es[k] = e),
인덱스 k를 부모 위치로 바꾼 뒤 반복. - 반복 종료 후 key를 최종 위치에 삽입.
정리
결과적으로 PriorityQueue의 삽입 연산은 “마지막 위치에 새 원소를 추가한 뒤, 부모와 비교하며 위로 올리는 과정(Heapify Up)”을 통해 힙 속성을 유지하며, 전체 시간 복잡도는 O(log N) 이다.