Fibonacci Heaps Implementation

Fibonacci Heap
-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

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

$\phi(H) = trees(H) + 2marks(H)$
mark -> lost a child
-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

Actual cost = O(1)
Change in potential = 0
Amortized cost = O(1)

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

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

  1. Starting from an empty data structure
  2. n = max # of elements in D at any time
  3. 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).



PISIKA Copyright © 2009