피보나치 힙을 다시 공부하게 되서 정리한 글.
흔히 피보나치 힙을 들으면 '피보나치 수열'을 떠올린다.
그리고 '힙'을 보면 떠오르는 '트리.. 힙?'이 있다.
정의로 따지면 둘 다 맞다.
우선 피보나치 힙이다보니 힙 구조를 가지게 된다.
힙의 주요 기능들 '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; }
'알고리즘' 카테고리의 다른 글
Alias method Algorithm (0) | 2023.04.27 |
---|---|
boids (0) | 2023.04.23 |
문자열 매칭 알고리즘 (0) | 2015.12.05 |
A* Algorithm (0) | 2015.11.25 |
GrahamScan Algorithm (0) | 2015.11.25 |