피보나치 하면 수열이 가장 먼저 떠오르는데 이 수열의 개념이 힙이 결합하는 과정과 유사하여
피보나치 힙이라고 불린다.
피보나치 힙은 각 힙들을 doubly circular linked list 형태로 구성되는데
피보나치 힙은 삽입의 과정을 거치면 이항 힙과 유사한 형태로 계속 같은 level의 min으로 추가 한다.
추가하면서 계속 min을 체크함.
* node * fb[MAX]의 노드포인터 배열을 선언하고
그리고 최소 값을 반환하는 순간 모양이 재조정되는데, 최소값을 가진 heap의 루트가 반환되고, 해당 heap의
자식노드들을 포인터로 기존 min level과 연결한다.
* 그리고 가장 최근에 삽입한 heap의 내부노드 수를 판단하여
해당 내부노드 수 값의 index에 해당 heap을 삽입한다.
* 그리고 다음 doubly circular linked list로 연결된 다음 heap을 가져와서 degree를 판단하여 해당 내부노드 수의 index에 값을 넣는데
만약 이미 해당 index에 값이 있다면 두 degree는 결합이 되어진다.
구현 참조 : https://github.com/beniz/fiboheap/blob/master/fiboheap.h
'Archived(CSE Programming) > 자료구조(C++)' 카테고리의 다른 글
스택(Stack)과 큐(Queue), 순환 큐(Circular Queue) (0) | 2020.11.23 |
---|---|
우선순위 큐_대칭 최소최대 힙(Symmetric min max heap) (0) | 2018.12.09 |
자료구조 프로그래밍 Lab09) Patricia 만들기 (0) | 2018.11.30 |
자료구조 프로그래밍 Lab08) BTree (2-3 Tree) 만들기 (3) | 2018.11.26 |
자료구조 프로그래밍 Lab07) AVL Tree 만들기 (0) | 2018.11.18 |