-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).
