Basic introduction to fibonacci heaps and some comparson with regular heaps.

## Operations Supported

`make_heap`

- Create a new heap.`insert(H, x)`

- Insert`x`

into heap`H`

.`min(H)`

- Return minimum element in`H`

.`extract_min(H)`

- Return minimum element in`H`

and removes it.`union(H1, H2)`

- Creates and returns a new heap containing all elements in`H1`

and`H2`

.`decrease_key(H, x, k)`

- Assigns`x`

in`H`

a new key`k`

.`k`

must be less then the current key.`delete(H, x)`

- Delete element`x`

from heap`H`

.

### Complexity Comparsions With Binary-Heaps

Binary Heap Worse-Case | Fib-Heap Amortized | |
---|---|---|

insert | $\Theta(lgn)$ | $\Theta(1)$ |

extract-min | $\Theta(lgn)$ | $O(lgn)$ |

decrease-priority | $\Theta(lgn)$ | $\Theta(1)$ |

union | $\Theta(n)$ | $\Theta(1)$ |

## Structure

A fibonnacci heap includes the following components:

- A forest of heap-ordered trees.
- Roots of these trees are stored in a circular doubly-linked list.
- Pointer to minimum root, and total number of nodes.
- Siblings in a circular doubly-linked list, parent only knows one child.
`deg(x)`

is number of children is`x`

’s child list.

For each node, it contains following fields:

- key: Priority
- left, right, parent: Pointers
- child: Pointer to one child
- degree: Num of children
- mark: Boolean, useful for
`decrease-priority`

## Operations

### Insert

Insert is very simple, you simply insert into the root linked-list. This takes $O(1)$.

```
insert(H, x) {
node = new Node(x);
node.marked = false;
// Insert right after H.min
node.right = H.min.right;
node.left = H.min;
H.min.right = node;
node.right.left = node;
}
```

### Union

Just merge two root lists and it is done. This also takes $O(1)$.

Of course if you want to make a copy this takes longer.

```
union(H1, H2) {
connect H1.min and H2.min
}
```