Fibonacci Heaps

Created: 2023-04-02T00:42:17-05:00

Return to the Index

This card pertains to a resource available on the internet.

Heap property: no element is smaller than its parent

Priority Queue

Priority Queue: stores nodes sorted by key, with the lowest/highest key always at the front of the queue.

Get Min: Retrieve lowest key in tree.

Extract Min: Remove lowest key from tree and rebalance the queue.

Insert: Put a new element in the queue.

Decrease Key: Raise the priority of an element already in the queue.

Degree: how many children are beneath a given node.

Binomial Tree: when trees are created by attaching sub-trees of identical sizes.

Fibonacci Heap

"Root list" stores all of the tree nodes which are siblings of the parent. The heap has an implicit parent all initial nodes belong to.

Each node also has a downward and upward pointer.

Get Min: store a pointer to the lowest node, so this is O(1)

Insert: Add a new tree with the new element; update minimum pointer if smaller

Extract Min: Must walk root set to find next minima; so use the opportunity to rebalance the root trees.

Extract Min

Merge tree: attach node with larger key as a child of one with a smaller key.

Lift children of the node being removed to the root list of nodes.

Calculate largest degree within the root set

Create [sparse] array with one slot per degree in the set

Walk the root set and place nodes in the array based on degree. If there is already something in that slot perform a tree merge. Bump the tree to its now location (based on post-merge degrees) possibly recursively merging as nodes are bumped from the array.

Decrease Min

Cut that particular node from its parent, modify the key, and insert it to the root set. Update pointer to the minimum node if its outdated. Future ExtractMin calls will rebalance the tree and fold the grafted tree back where it belongs--eventually.

Cut out a node

"Cut at most one child per node."

If cutting the node causes the parent to lose only one child in total, the parent nodes are also cut. This recurses for each parent node that has its total depth reduced by exactly one due to a removal operation.

Cut nodes are rebalanced in the next ExtractMin.