티스토리 뷰
유용한 링크: 위키백과, Skew heap visualization, NTU 강의자료
Skew heap(혹은 self-adjusting heap)은 이진트리로 구현된 힙 자료구조다. 우리가 배운 기본적인 힙은 완전이진트리이므로 배열과 인덱스를 이용하여 편하게 구현이 가능하다. 그러나, Skew heap은 완전이진트리가 아닌 그냥 이진트리이므로 배열을 이용한 구현을 할 수 없다.
그렇다면, 일반 힙이 아닌 Skew heap이 필요한 순간은 언제일까? 바로, 서로 다른 두 힙을 하나로 빠르게 합치고 싶은 순간에 쓸 수 있다. 서로 다른 두 힙을 하나로 합치는 것을 merge 연산이라고 한다. Skew heap은 merge 연산 중간, 왼쪽 자식과 오른쪽 자식을 무조건적으로 바꿔주어 균형을 유지한다. 이 merge 연산은 Skew heap에 원소를 추가(push)하거나, 루트에 있는 값을 제거(pop)할 때도 사용된다. 힙이 균형잡혀 있기 때문에 merge 연산은 amortised $O(\lg n)$ 시간복잡도를 가진다. 좀 더 정확히 하자면, 황금비 $\varphi = \frac{1+\sqrt{5}}{2}$가 있을 때, $O(\log_{\varphi} n)$이 된다. 이는 약 $1.44 \lg n$이다.
Skew heap은 다음과 같이 정의된다:
1. 원소가 하나인 힙은 Skew heap이다.
2. 두 Skew heap을 merge한 결과는 Skew heap이다.
이제 두 Skew heap을 하나로 합치는 merge 연산이 어떻게 동작하는지 알아보자. Merge 연산이 하는 일은 다음과 같다:
1. 합치려고 하는 두 Skew heap 중 루트가 작은 것을 $t_1$, 나머지를 $t_2$라 하자. 그리고 만들려고 하는 새로운 힙을 $r$이라 하자.
2. $r$의 루트는 $t_1$의 루트가 되며, $r$의 오른쪽 서브트리는 $t_1$의 왼쪽 서브트리가 된다.
3. 재귀적으로 $t_2$와 $t_1$의 오른쪽 서브트리를 합쳐 하나의 힙으로 만든 뒤, 그 힙을 $r$의 왼쪽 서브트리로 둔다.
다음은 merge 연산의 예시이다:
마지막으로, push와 pop은 어떻게 구현할 수 있을까? 원소를 삽입하는 것은 크기가 1인 Skew heap과의 merge로 구현할 수 있고, 루트를 삭제하는 것은 루트의 왼쪽 서브트리에 해당하는 Skew heap과 오른쪽 서브트리에 해당하는 Skew heap을 합치는 것으로 구현할 수 있다.
Skew heap을 C++으로 구현하면 다음과 같다.
Skew heap은 Hu-Tucker algorithm을 구현할 때 활용할 수 있다.
'공부' 카테고리의 다른 글
다항식 나눗셈의 몫을 빠르게 구하는 방법 (1) | 2022.11.29 |
---|---|
Hu-Tucker Algorithm (0) | 2022.05.03 |
Z-function (2) | 2021.03.08 |
Li Chao Tree (Dynamic Convex Hull Optimization) (0) | 2021.03.08 |
Stern-Brocot 트리 (0) | 2019.05.21 |
- Total
- Today
- Yesterday
- BOI 2009
- IOI2014
- Dijkstra
- idea
- Boyer
- Knuth Optimization
- BOI
- Parametric Search
- ioi
- majority
- BOI 2001
- dynamic programming
- optimization
- Splay Tree
- IOI2013
- moore
- TRIE
- HackerRank
- Tree
- Greedy Method
- IOI2011
- Divide & Conquer
- Segment tree
- z-trening
- USACO
- IOI2012
- Algorithm
- Boyer-Moore Majority Vote Algorithm
- vote
- Dynamic Pramming
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |