이항 힙과 마찬가지로 피보나치 힙은 트리 모음입니다. 느슨하게 이항 힙을 기반으로 합니다. 이항 힙이 있는 트리와 달리 피보나치 힙 내의 정렬된 트리는 루트가 있지만 정렬되지 않습니다.
피보나치 힙의 각 노드 x에는 부모에 대한 포인터 p[x]와 자식 중 하나에 대한 포인터 자식[x]가 포함되어 있습니다. x의 자식은 x의 자식 목록으로 알려진 순환 이중 연결 목록에서 함께 연결됩니다. 자식 목록의 각 자식 y에는 각각 y의 왼쪽 및 오른쪽 형제를 가리키는 왼쪽[y] 및 오른쪽[y] 포인터가 있습니다. 노드 y가 유일한 자식이면 왼쪽[y] =오른쪽[y] =y입니다. 형제가 자식 목록에 나타나는 순서는 임의적입니다.
피보나치 힙의 예
이 피보나치 힙 H는 5개의 피보나치 힙과 16개의 노드로 구성됩니다. 화살촉이 있는 선은 루트 목록을 나타냅니다. 목록의 최소 노드는 4를 유지하는 min[H]로 표시됩니다.
최소 스패닝 트리 계산, 최단 경로의 단일 소스 찾기 등과 같은 문제에 대한 점근적으로 빠른 알고리즘은 피보나치 힙을 필수적으로 사용합니다.