티스토리 뷰

공부

Skew Heap

전명우 2022. 5. 3. 02:00

유용한 링크: 위키백과, 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 연산의 예시이다:

<그림 1> 합치려고 하는 두 Skew Heap
<그림 2> 합쳐진 결과

마지막으로, push와 pop은 어떻게 구현할 수 있을까? 원소를 삽입하는 것은 크기가 1인 Skew heap과의 merge로 구현할 수 있고, 루트를 삭제하는 것은 루트의 왼쪽 서브트리에 해당하는 Skew heap과 오른쪽 서브트리에 해당하는 Skew heap을 합치는 것으로 구현할 수 있다.

 

Skew heap을 C++으로 구현하면 다음과 같다.

 

Skew heap은 Hu-Tucker algorithm을 구현할 때 활용할 수 있다.

'공부' 카테고리의 다른 글

Hu-Tucker Algorithm  (0) 2022.05.03
Skew Heap  (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
트리의 지름 구하기  (5) 2016.10.11
댓글
댓글쓰기 폼