Giống như Binomial heap, Fibonacci heap là tập hợp các cây. Chúng dựa trên binomial heap nhưng lỏng lẻo hơn: cây trong binomial heap là có thứ tự (ordered), trong Fibonacci heap là cây gốc (rooted) nhưng không có thứ tự (unordered).
Mỗi nút x trong Fibonacci heap chứa con trỏ p[x] đến cha, và child[x] đến một trong các con. Các con của x được liên kết trong danh sách liên kết đôi vòng (circular doubly linked list) gọi là child list của x. Mỗi con y trong child list có con trỏ left[y] và right[y] trỏ đến anh chị em trái/phải. Nếu y là con duy nhất thì left[y] = right[y] = y. Thứ tự anh chị em trong child list tùy ý.
Ví dụ Fibonacci Heap
Fibonacci Heap H này gồm năm heap con và 16 nút. Đường mũi tên chỉ root list. Nút nhỏ nhất là min[H] = 4.
Các thuật toán tiệm cận nhanh cho bài toán cây bao trùm tối thiểu (MST), đường đi ngắn nhất từ một nguồn (single-source shortest paths) sử dụng thiết yếu Fibonacci heap.