랜덤화 힙¶
랜덤화 힙은 무작위성을 이용하여 모든 연산을 기대 로그 시간에 수행할 수 있게 하는 힙입니다.
최소 힙은 각 정점의 값이 그 자식들의 값보다 작거나 같은 이진 트리입니다. 따라서 트리의 최솟값은 항상 루트 정점에 있습니다.
최대 힙도 비슷한 방식으로 정의할 수 있습니다. "작거나 같다"를 "크거나 같다"로 바꾸면 됩니다.
힙의 기본 연산은 다음과 같습니다.
- 값 추가
- 최솟값 추출
- 최솟값 제거
- 두 힙의 병합 (중복을 제거하지 않음)
- 임의의 원소 제거 (트리에서 그 위치를 알고 있는 경우)
랜덤화 힙은 매우 간단한 구현으로 이 모든 연산을 기대 $O(\log n)$ 시간에 수행할 수 있습니다.
자료 구조¶
이진 힙의 구조는 바로 다음과 같이 설명할 수 있습니다.
struct Tree {
int value;
Tree * l = nullptr;
Tree * r = nullptr;
};
정점에는 값을 저장합니다. 또한 왼쪽 자식과 오른쪽 자식을 가리키는 포인터를 두며, 해당 자식이 없으면 포인터는 null을 가리킵니다.
연산¶
모든 연산이 단 하나의 연산, 즉 두 힙을 하나로 병합하는 연산으로 귀결된다는 것은 어렵지 않게 알 수 있습니다. 실제로 힙에 새 값을 추가하는 것은 그 힙을 해당 값을 가진 정점 하나로 이루어진 힙과 병합하는 것과 같습니다. 최솟값을 찾는 데에는 아무런 연산도 필요하지 않습니다. 최솟값은 그저 루트에 있는 값입니다. 최솟값을 제거하는 것은 루트 정점의 왼쪽 자식과 오른쪽 자식을 병합한 결과와 같습니다. 임의의 원소를 제거하는 것도 비슷합니다. 해당 정점의 자식들을 병합하고 그 정점을 병합 결과로 대체합니다.
따라서 실제로는 두 힙을 병합하는 연산만 구현하면 됩니다. 다른 모든 연산은 이 연산으로 자명하게 귀결됩니다.
두 힙 $T_1$과 $T_2$가 주어졌다고 합시다. 각 힙의 루트에는 그 힙의 최솟값이 들어 있음이 분명합니다. 따라서 결과 힙의 루트는 이 두 값 중 최솟값이 됩니다. 그러므로 두 값을 비교하여 더 작은 값을 새 루트로 사용합니다. 이제 선택된 정점의 자식들을 나머지 힙과 합쳐야 합니다. 이를 위해 자식 중 하나를 선택하여 나머지 힙과 병합합니다. 따라서 다시 두 힙을 병합하는 연산을 수행하게 됩니다. 이 과정은 언젠가는 끝납니다(이러한 단계의 수는 두 힙의 높이의 합으로 제한됩니다)
평균적으로 로그 복잡도를 달성하려면, 평균 경로 길이가 로그가 되도록 두 자식 중 하나를 선택하는 방법을 정해야 합니다. 이 결정을 무작위로 내리게 된다는 것은 어렵지 않게 짐작할 수 있습니다. 따라서 병합 연산의 구현은 다음과 같습니다:
Tree* merge(Tree* t1, Tree* t2) {
if (!t1 || !t2)
return t1 ? t1 : t2;
if (t2->value < t1->value)
swap(t1, t2);
if (rand() & 1)
swap(t1->l, t1->r);
t1->l = merge(t1->l, t2);
return t1;
}
여기서는 먼저 두 힙 중 하나가 비어 있는지 확인하며, 비어 있다면 병합 작업을 전혀 수행할 필요가 없습니다. 그렇지 않으면 힙 t1이 더 작은 값을 가진 힙이 되도록 합니다(필요하면 t1과 t2를 교환합니다). t1의 왼쪽 자식을 t2와 병합하려 하므로, t1의 자식들을 무작위로 교환한 다음 병합을 수행합니다.
복잡도¶
루트에서 리프까지의 무작위 경로의 길이(간선 수로 센 길이)를 나타내는 확률 변수 $h(T)$를 도입합니다. 알고리즘 merge가 $O(h(T_1) + h(T_2))$번의 단계를 수행한다는 것은 분명합니다. 따라서 연산의 복잡도를 이해하려면 확률 변수 $h(T)$를 살펴보아야 합니다.
기댓값¶
$h(T)$의 기댓값이 힙의 정점 수의 로그로 위에서 추정될 수 있다고 가정합니다:
이는 귀납법으로 쉽게 증명할 수 있습니다. $L$과 $R$을 루트 $T$의 왼쪽과 오른쪽 서브트리라 하고, $n_L$과 $n_R$을 각각의 정점 수라 합시다($n = n_L + n_R + 1$).
다음은 귀납법의 귀납 단계를 보여 줍니다:
기댓값을 초과하는 경우¶
물론 아직 만족스럽지는 않습니다. $h(T)$의 기댓값은 최악의 경우에 대해 아무것도 말해 주지 않습니다. 특정 트리에서는 루트에서 정점까지의 경로가 평균적으로 $\log(n + 1)$보다 훨씬 클 가능성이 여전히 있습니다.
기댓값을 초과할 확률이 실제로 매우 작다는 것을 증명해 봅시다:
이는 임의의 양의 상수 $c$에 대해 성립합니다.
여기서 $P$는 힙의 루트에서 리프까지의 경로 중 길이가 $(c+1) \log n$을 초과하는 경로들의 집합을 나타냅니다. 길이가 $|p|$인 임의의 경로 $p$가 무작위 경로로 선택될 확률은 $2^{-|p|}$임에 유의하십시오. 따라서 다음을 얻습니다:
알고리즘의 복잡도¶
따라서 merge 알고리즘과, 그에 따라 이를 이용해 표현되는 다른 모든 연산은 평균적으로 $O(\log n)$에 수행할 수 있습니다.
또한 임의의 양의 상수 $\epsilon$에 대해, 연산에 $c \log n$보다 많은 단계가 필요할 확률이 $n^{-\epsilon}$보다 작아지도록 하는 양의 상수 $c$가 존재합니다(어떤 의미에서 이는 알고리즘의 최악의 경우 동작을 설명합니다).