본문 바로가기

Archived(CSE Programming)/자료구조(C++)

우선순위 큐_피보나치 힙(Fibonacci Heap)


피보나치 하면 수열이 가장 먼저 떠오르는데 이 수열의 개념이 힙이 결합하는 과정과 유사하여

피보나치 힙이라고 불린다.


피보나치 힙은 각 힙들을 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