<div id="readability-page-1" class="page"><div>유용한 링크: <a href="https://en.wikipedia.org/wiki/Skew_heap#:~:text=A%20skew%20heap%20(or%20self,more%20quickly%20than%20binary%20heaps." target="_blank" rel="noopener">위키백과</a>, <a href="https://www.cs.usfca.edu/~galles/visualization/SkewHeap.html" target="_blank" rel="noopener">Skew heap visualization</a>, <a href="http://ccf.ee.ntu.edu.tw/~yen/courses/ds17/chapter-6d.pdf" target="_blank" rel="noopener">NTU 강의자료</a>

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 연산의 예시이다:
<figure data-origin-width="360" data-origin-height="116" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/psJeO/btrA5a712ye/HBZVN49j4tbqiF6yVILuCk/img.png" data-ke-mobilestyle="alignCenter"><figcaption>&lt;그림 1&gt; 합치려고 하는 두 Skew Heap</figcaption></figure><figure data-origin-width="279" data-origin-height="255" data-ke-mobilestyle="alignCenter"><img src="https://blog.kakaocdn.net/dn/c3SoT9/btrA5rnNvCI/r8vTRzPK2zF6OjTCWp1Ca0/img.png" data-ke-mobilestyle="alignCenter"><figcaption>&lt;그림 2&gt; 합쳐진 결과</figcaption></figure>
마지막으로, push와 pop은 어떻게 구현할 수 있을까? 원소를 삽입하는 것은 크기가 1인 Skew heap과의 merge로 구현할 수 있고, 루트를 삭제하는 것은 루트의 왼쪽 서브트리에 해당하는 Skew heap과 오른쪽 서브트리에 해당하는 Skew heap을 합치는 것으로 구현할 수 있다.

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


Skew heap은 <a href="https://mwchun.tistory.com/141" target="_blank" rel="noopener">Hu-Tucker algorithm</a>을 구현할 때 활용할 수 있다.</div></div>

PS 이야기

유용한 링크: 위키백과, 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++으로 구현하면 다음과 같다.
#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct SkewHeap{
	using value_t = T;
	struct Node;
	using node_t = Node;
	using nodeptr_t = unique_ptr<node_t>;
	struct Node{
		Node() = default;
		Node(const T& value): value(value){}
		value_t value;
		nodeptr_t left = nullptr, right = nullptr;
		static nodeptr_t merge(nodeptr_t t1, nodeptr_t t2){
			if (t1 == nullptr) return t2;
			if (t2 == nullptr) return t1;
			if (t2->value < t1->value) return merge(move(t2), move(t1));
			nodeptr_t tmp = move(t1->right);
			t1->right = move(t1->left);
			t1->left = merge(move(t2), move(tmp));
			return t1;
		}
	};
	nodeptr_t m_root{};
	size_t m_size{};
	bool empty()const{ return m_size == 0; }
	size_t size()const{ return m_size; }
	value_t top()const{
		return m_root->value;
	}
	value_t second_top()const{
		if (m_root->left == nullptr) return m_root->right->value;
		if (m_root->right == nullptr) return m_root->left->value;
		return min(m_root->left->value, m_root->right->value);
	}
	value_t pop(){
		--m_size;
		auto value = m_root->value;
		m_root = node_t::merge(move(m_root->left), move(m_root->right));
		return value;
	}
	void push(const value_t& value){
		++m_size;
		m_root = node_t::merge(move(m_root), nodeptr_t{new node_t(value)});
	}
	void merge(SkewHeap<value_t>&& other){
		m_size += other.m_size;
		m_root = node_t::merge(move(m_root), move(other.m_root));
		other.m_size = 0;
		other.m_root = nullptr;
	}
};
 
Skew heap은 Hu-Tucker algorithm을 구현할 때 활용할 수 있다.

Skew Heap

댓글