-represent tress using left-child, right sibling pointers and circular

-roots of trees connected w/ circular doubly-linked list

-pointer to root of tree w/ minimum elements

Notation

n = number of nodes in heap

rank(x) = number of children of node x

rank(H) = max rank of any node in heap H

trees(H) = number of trees in heap H

marks(H) = number of marked nodes in H

Potential:

$\phi(H) = trees(H) + 2marks(H)$

mark -> lost a child

**Insert**

-create a new singleton tree

-add to the left of min pointer

-update min pointer

Actual cost = O(1)

Chage in potential = +1

Amortized cost = +1

**Union**

Actual cost = O(1)

Change in potential = 0

Amortized cost = O(1)

**Delete-min**

-delete min & concatenate its children into root list

-consolidate trees so that no two roots have same degree

Operation | Binary | Binomial | Fibonacci |
---|---|---|---|

makeheap | $O(1)$ | $O(1)$ | $O(1)$ |

heapify | $O(n)$ | $O(n)$ | $O(n)$ |

findmin | $O(1)$ | $O(1)$ | $O(1)$ |

insert | $O(\lg n)$ | $O(\lg n)$ | $O(1)$ |

delete-min | $O(\lg n)$ | $O(\lg n)$ | $O(\lg n)$ |

delete-node | $O(\lg n)$ | $O(\lg n)$ | $O(\lg n)$ |

decrease-key | $O(\lg n)$ | $O(\lg n)$ | $O(1)^{**}$ |

meld/merge | $O(m+n)$ | $O(\lg n)^{*}$ | $O(1)$ |

**Amortized

*n is is the size of the larger heap, $O(1)$ for lazy meld

**Amortization in General**

Given a finite collection C of operations on a data structure D the amortized cost of an operation is the max average cost of that operation in any sequence of operations.

- Starting from an empty data structure
- n = max # of elements in D at any time
- is defined only in relation to amortized cost of all other operations

Theorem: It is not possible to do both insert and delete-min each in O(1) amortized, else it would be posible to sort in O(n).