피보나치 힙

피보나치 힙을 다시 공부하게 되서 정리한 글.

 

흔히 피보나치 힙을 들으면 '피보나치 수열'을 떠올린다.

그리고 '힙'을 보면 떠오르는 '트리.. 힙?'이 있다.

정의로 따지면 둘 다 맞다.

우선 피보나치 힙이다보니 힙 구조를 가지게 된다.

힙의 주요 기능들 'INSERT, MINIMUM, EXTRACT-MIN, UNION, DECREASE-KEY, DELETE' 연산이 필수적이다.

하지만 그냥 힙구조 쓰면 되지가 아니라ㅎ 성능상 이점이 다르다.

Operation	Binary[6]	Binomial[6]	Fibonacci[6]	Pairing[7]	Brodal[8][a]	Rank-pairing[10]	Strict Fibonacci[11]
find-min	Θ(1)	Θ(1)	Θ(1)	Θ(1)	Θ(1)	Θ(1)	Θ(1)
delete-min	Θ(log n)	Θ(log n)	O(log n)[b]	O(log n)[b]	O(log n)	O(log n)[b]	O(log n)
insert	Θ(log n)	Θ(1)[b]	Θ(1)	Θ(1)	Θ(1)	Θ(1)	Θ(1)
decrease-key	Θ(log n)	Θ(log n)	Θ(1)[b]	o(logn)[b][c]	Θ(1)	Θ(1)[b]	Θ(1)
merge	Θ(n)	O(log n)[d]	Θ(1)	Θ(1)	Θ(1)	Θ(1)	Θ(1)

출처 : wiki

 

흔히 자주 쓰는 이진(Binary)는 Θ(logn )을 띄는 반면에 Fibonacci는 Θ(1)을 기대할 수 있다(?!)

와우, 이러면 무조건 Fibonacci 쓰는게 좋은건가요? 할 수 있지만;

실용적인 관점에서 구현의 복잡성(-ㅅ-)과 일반적인 프로그램에서는 이진 힙보다 이점을 크게 얻을 수 없다..

반면에 그래프 문제와 간선이 많은 조밀한 그래프에서 이진(Binary)나 이항(Binomial)에 비해 큰 이점을 얻을 수 있다.

(피보나치 힙을 일반적으로 최소 신장트리, 단일 출발지 최단 경로를 찾는 문제에서 많이 쓴다)

결론은 피보나치 힙은 한정된 상황에서 큰 이점을 가져다 주는 알고리즘이지만 더 간단한 자료구조를 사용해야 널리 쓰일 수 있다.

 

이항 힙과 유사한 피보나치 힙은 순서를 갖는 최소 힙 트리의 모임이다. 다만 피보나치 힙의 트리가 반드시 이항 트리일 필요는 없다. 또한, SEARCH 연산에는 효율적이지 않으므로 포인터를 사용해서 접근해야 좀더 편하다.

위 그림이 피보나치 힙의 모양을 보여준다.

 

자세한 설명은 책에서 보기로 하고ㅜ

코드는 오픈소스 https://github.com/beniz/fiboheap/blob/master/fiboheap.h

또는 아래에 적어둔다.

/*
Private Function ***********/

/* 링크드리스트에 추가, 일반적으로 자식 리스트.
 */
void join_list(NODE* src, NODE* add)
{
	NODE *rr;

	rr = src->right;
	src->right = add;
	add->left = src;
	add->right = rr;
	rr->left = add;
}
/* 링크드리스트에서 삭제, 일반적으로 자식리스트
 * 제거된 노드는 고립된 노드가 된다(left,right 는 자신을 가리키고 parent = NULL)
 * child 를 가리키는 포인터는 수정하지 않음.
 */
void rm_list(NODE* n_rm)
{
	NODE *ll;
	NODE *rr;
	ll = n_rm->left;
	rr = n_rm->right;

	if (n_rm->parent != NULL)
	{
		NODE *pp;
		pp = n_rm->parent;

		if (n_rm->right == n_rm)
			pp->child = NULL;
		else
		{
			pp->child = n_rm->right;

			ll->right = rr;
			rr->left = ll;
		}
	}
	else
	{
		ll->right = rr;
		rr->left = ll;
	}
	n_rm->parent = NULL;
	n_rm->left = n_rm->right = n_rm;
}
/* 루트리스트에 추가, 내부적으로 join_list 호출
 */
void add_root(HEAP *hp_src, NODE *n_add)
{
	n_add->parent = NULL;

	if (hp_src->root == NULL)
		hp_src->root = n_add;
	else
		join_list(hp_src->root, n_add);
}
/* 루트리스트에서 제거, 내부적으로 rm_list 호출
 */
void del_root(HEAP *hp_src, NODE *n_del)
{
	if (n_del->right == n_del)
	{
		hp_src->root = NULL;
		n_del->left = n_del->right = n_del;
	}
	else	
	{
		if (hp_src->root == n_del)
			hp_src->root = n_del->right;

		rm_list(n_del);
	}
}
/* Fib Heap Link
 * n_child 를 n_parent 의 자식노드로 하여 결합
 * 부모-자식 관계가 바뀌므로 링크 연결에 주의
 */
void heap_link(HEAP* h_link, NODE* n_child, NODE* n_parent)
{
	if (n_parent->child == NULL)
	{
		n_parent->child = n_child;
		n_child->parent = n_parent;
		n_child->left = n_child->right = n_child;
	}
	else
	{
		NODE *rr;
		rr = n_parent->child->right;

		n_parent->child->right = n_child;
		n_child->left = n_parent->child;
		n_child->right = rr;
		rr->left = n_child;
	}
	n_child->parent = n_parent;
	n_parent->degree++;
	n_child->mark = FALSE;
}
/* Fib Cut
 * y 의 자식노드인 x 를 잘라냄
 */
void fib_cut(HEAP *hp, NODE *x, NODE *y)
{
	rm_list(x);
	y->degree--;
	add_root(hp, x);
	x->parent = NULL;
	x->mark = FALSE;
}
/* Fib cascading cut
 */
void fib_cas_cut(HEAP *hp, NODE *y)
{
	NODE *z;
	z = y->parent;
	if (z != NULL)
	{
		if (y->mark == FALSE)
			y->mark = TRUE;
		else
		{
			fib_cut(hp, y, z);
			fib_cas_cut(hp, z);
		}
	}
}
/* Heap 을 재구성
 * 도중에 exchange 가 되면 x 와 y 가 바뀌어야 한다.
 */
void consolidate(HEAP* hp_con)
{
	unsigned int D_n = 1;
	unsigned int po = 1;
	while (po < hp_con->nodes)
	{
		po = po << 1;
		D_n++;
	}

	NODE **arr = (NODE **)malloc(sizeof(NODE *)* (D_n));

	NODE *w;
	NODE *x;
	NODE *y;

	for (unsigned int i = 0; i < D_n; i++)
		arr[i] = NULL;

	while (hp_con->root != NULL)
	{
		unsigned int d;

		x = hp_con->root;
		d = x->degree;
		del_root(hp_con, x);

		while (arr[d] != NULL)
		{
			y = arr[d];

			if (x->key > y->key)
			{
				w = x;
				x = y;
				y = w;
			}
			heap_link(hp_con, y, x);

			arr[d] = NULL;
			d++;
		}

		arr[d] = x;
	}

	hp_con->min = NULL;

	for (unsigned int i = 0; i < D_n; i++)
	{
		if (arr[i] != NULL)
		{
			add_root(hp_con, arr[i]);
			if (hp_con->min == NULL || arr[i]->key < hp_con->min->key)
				hp_con->min = arr[i];
		}
	}

	free(arr);
}

/*
Public Function ***********/

/* 힙 생성
 */
HEAP* new_fibheap(void)
{
	HEAP *fib;
	fib = (HEAP *)malloc(sizeof(HEAP));
	fib->nodes = 0;
	fib->min = NULL;
	fib->root = NULL;

	return fib;
}
/* 노드 생성
 */
NODE* new_fibnode(node data, int key)
{
	NODE *n_new;
	n_new = (NODE *)malloc(sizeof(NODE));

	n_new->data = data;
	n_new->key = key;
	n_new->left = n_new->right = n_new;
	n_new->parent = NULL;
	n_new->child = NULL;

	return n_new;
}
/* Fib Extract Min
 * Heap 에서 min 이 가리키는 노드를 찾아 Heap 에서 제거하고
 * (실제 삭제되지는 않고 링크만 끊어짐) 노드의 포인터를 반환
 * min 의 모든 자식들을 루트리스트에 추가한다.
 * 리턴되는 노드는 고립된 노드가 된다.
 */
NODE *fib_extr_min(HEAP *hp)
{
	NODE *min_node;
	min_node = hp->min;

	if (min_node != NULL)
	{
		NODE *child_node;
		child_node = min_node->child;

		if (child_node == NULL);
		else
		{
			while (min_node->child != NULL)
			{
				rm_list(child_node);
				add_root(hp, child_node);
				child_node = min_node->child;
			}
		}

		del_root(hp, min_node);

		if (hp->root == NULL)
			hp->min = NULL;
		else
		{
			hp->min = hp->root;
			consolidate(hp);
		}

		hp->nodes--;	
	}

	return min_node;
}
/* fibnode 를 추가하는 함수
 */
void fib_insert(HEAP* Hp, NODE* node)
{
	node->degree = 0;
	node->parent = NULL;
	node->child = NULL;
	node->left = node;
	node->right = node;
	node->mark = FALSE;

	add_root(Hp, node);

	if (Hp->min == NULL || node->key < Hp->min->key)
		Hp->min = node;
	Hp->nodes++;
}
/* Fib Decrease key
 * 노드의 키값을 감소시키는 함수
 * 키값이 감소하면 자식들에 대해 모두 재조정을 한다.
 */
void fib_desc_key(HEAP *hp, NODE *x, int k)
{
	if (k > x->key)
		printf("desc_key error : new key is greater than current key\n");
	x->key = k;
	NODE *y;
	y = x->parent;
	if (y != NULL && x->key < y->key)
	{
		fib_cut(hp, x, y);
		fib_cas_cut(hp, y);
	}
	if (x->key < hp->min->key)
		hp->min = x;
}
/* Destroy fibheap
 * Heap 을 삭제. 남아있는 노드가 있으면 에러를 리턴한다.
 */
int destroy_heap(HEAP *hp)
{
	if (hp->nodes == 0)
		free(hp);
	else
	{
		printf("destroy_heap error : there's %d nodes\n", hp->nodes);
		return FALSE;
	}
	return TRUE;
}