Fibonacci heap

Fibonacci heap is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Fibonacci heap

Task

• Implement queue operations for fibonacci heaps. Where H is heap, x node with data value, k integer.
• Operations:
  • MakeHeap() - create new empty Fibonacci heap
  • Insert(H,x) - insert new element x into heap H
  • Union(H1, H2) - union heap H1 and heap H2
  • Minimum(H) - return minimum value from heap H
  • ExtractMin(H) - (or DeleteMin(H)) - return minimum value from heap H and remove it from heap
  • DecreaseKey(H,x,k) - ecrease value of element x in heap H to value k
  • Delete(H,x) - remove element x from heap H

Contents

Python

<lang forth> class FibonacciHeap:

   # internal node class 
   class Node:
       def __init__(self, data):
           self.data = data
           self.parent = self.child = self.left = self.right = None
           self.degree = 0
           self.mark = False
           
   # function to iterate through a doubly linked list
   def iterate(self, head):
       node = stop = head
       flag = False
       while True:
           if node == stop and flag is True:
               break
           elif node == stop:
               flag = True
           yield node
           node = node.right
   
   # pointer to the head and minimum node in the root list
   root_list, min_node = None, None
   
   # maintain total node count in full fibonacci heap
   total_nodes = 0
   
   # return min node in O(1) time
   def find_min(self):
       return self.min_node
        
   # extract (delete) the min node from the heap in O(log n) time
   # amortized cost analysis can be found here (http://bit.ly/1ow1Clm)
   def extract_min(self):
       z = self.min_node
       if z is not None:
           if z.child is not None:
               # attach child nodes to root list
               children = [x for x in self.iterate(z.child)]
               for i in xrange(0, len(children)):
                   self.merge_with_root_list(children[i])
                   children[i].parent = None
           self.remove_from_root_list(z)
           # set new min node in heap
           if z == z.right:
               self.min_node = self.root_list = None
           else:
               self.min_node = z.right
               self.consolidate()
           self.total_nodes -= 1
       return z
                   
   # insert new node into the unordered root list in O(1) time
   def insert(self, data):
       n = self.Node(data)
       n.left = n.right = n
       self.merge_with_root_list(n)
       if self.min_node is None or n.data < self.min_node.data:
           self.min_node = n
       self.total_nodes += 1
       
   # modify the data of some node in the heap in O(1) time
   def decrease_key(self, x, k):
       if k > x.data:
           return None
       x.data = k
       y = x.parent
       if y is not None and x.data < y.data:
           self.cut(x, y)
           self.cascading_cut(y)
       if x.data < self.min_node.data:
           self.min_node = x
           
   # merge two fibonacci heaps in O(1) time by concatenating the root lists
   # the root of the new root list becomes equal to the first list and the second
   # list is simply appended to the end (then the proper min node is determined)
   def merge(self, h2):
       H = FibonacciHeap()
       H.root_list, H.min_node = self.root_list, self.min_node
       # fix pointers when merging the two heaps
       last = h2.root_list.left
       h2.root_list.left = H.root_list.left
       H.root_list.left.right = h2.root_list
       H.root_list.left = last
       H.root_list.left.right = H.root_list
       # update min node if needed
       if h2.min_node.data < H.min_node.data:
           H.min_node = h2.min_node
       # update total nodes
       H.total_nodes = self.total_nodes + h2.total_nodes
       return H
       
   # if a child node becomes smaller than its parent node we
   # cut this child node off and bring it up to the root list
   def cut(self, x, y):
       self.remove_from_child_list(y, x)
       y.degree -= 1
       self.merge_with_root_list(x)
       x.parent = None
       x.mark = False
   
   # cascading cut of parent node to obtain good time bounds
   def cascading_cut(self, y):
       z = y.parent
       if z is not None:
           if y.mark is False:
               y.mark = True
           else:
               self.cut(y, z)
               self.cascading_cut(z)
   
   # combine root nodes of equal degree to consolidate the heap
   # by creating a list of unordered binomial trees
   def consolidate(self):
       A = [None] * self.total_nodes
       nodes = [w for w in self.iterate(self.root_list)]
       for w in xrange(0, len(nodes)):
           x = nodes[w]
           d = x.degree
           while A[d] != None:
               y = A[d] 
               if x.data > y.data:
                   temp = x
                   x, y = y, temp
               self.heap_link(y, x)
               A[d] = None
               d += 1
           A[d] = x
       # find new min node - no need to reconstruct new root list below
       # because root list was iteratively changing as we were moving 
       # nodes around in the above loop
       for i in xrange(0, len(A)):
           if A[i] is not None:
               if A[i].data < self.min_node.data:
                   self.min_node = A[i]
       
   # actual linking of one node to another in the root list
   # while also updating the child linked list
   def heap_link(self, y, x):
       self.remove_from_root_list(y)
       y.left = y.right = y
       self.merge_with_child_list(x, y)
       x.degree += 1
       y.parent = x
       y.mark = False
       
   # merge a node with the doubly linked root list   
   def merge_with_root_list(self, node):
       if self.root_list is None:
           self.root_list = node
       else:
           node.right = self.root_list.right
           node.left = self.root_list
           self.root_list.right.left = node
           self.root_list.right = node
           
   # merge a node with the doubly linked child list of a root node
   def merge_with_child_list(self, parent, node):
       if parent.child is None:
           parent.child = node
       else:
           node.right = parent.child.right
           node.left = parent.child
           parent.child.right.left = node
           parent.child.right = node
           
   # remove a node from the doubly linked root list
   def remove_from_root_list(self, node):
       if node == self.root_list:
           self.root_list = node.right
       node.left.right = node.right
       node.right.left = node.left
       
   # remove a node from the doubly linked child list
   def remove_from_child_list(self, parent, node):
       if parent.child == parent.child.right:
           parent.child = None
       elif parent.child == node:
           parent.child = node.right
           node.right.parent = parent
       node.left.right = node.right
       node.right.left = node.left

</lang>

C++

<lang forth> template <class V> class FibonacciHeap;

template <class V> struct node { private: node<V>* prev; node<V>* next; node<V>* child; node<V>* parent; V value; int degree; bool marked; public: friend class FibonacciHeap<V>; node<V>* getPrev() {return prev;} node<V>* getNext() {return next;} node<V>* getChild() {return child;} node<V>* getParent() {return parent;} V getValue() {return value;} bool isMarked() {return marked;}

bool hasChildren() {return child;} bool hasParent() {return parent;} };

template <class V> class FibonacciHeap { protected: node<V>* heap; public:

FibonacciHeap() { heap=_empty(); } virtual ~FibonacciHeap() { if(heap) { _deleteAll(heap); } } node<V>* insert(V value) { node<V>* ret=_singleton(value); heap=_merge(heap,ret); return ret; } void merge(FibonacciHeap& other) { heap=_merge(heap,other.heap); other.heap=_empty(); }

bool isEmpty() { return heap==NULL; }

V getMinimum() { return heap->value; }

V removeMinimum() { node<V>* old=heap; heap=_removeMinimum(heap); V ret=old->value; delete old; return ret; }

void decreaseKey(node<V>* n,V value) { heap=_decreaseKey(heap,n,value); }

node<V>* find(V value) { return _find(heap,value); } private: node<V>* _empty() { return NULL; }

node<V>* _singleton(V value) { node<V>* n=new node<V>; n->value=value; n->prev=n->next=n; n->degree=0; n->marked=false; n->child=NULL; n->parent=NULL; return n; }

node<V>* _merge(node<V>* a,node<V>* b) { if(a==NULL)return b; if(b==NULL)return a; if(a->value>b->value) { node<V>* temp=a; a=b; b=temp; } node<V>* an=a->next; node<V>* bp=b->prev; a->next=b; b->prev=a; an->prev=bp; bp->next=an; return a; }

void _deleteAll(node<V>* n) { if(n!=NULL) { node<V>* c=n; do { node<V>* d=c; c=c->next; _deleteAll(d->child); delete d; } while(c!=n); } }

void _addChild(node<V>* parent,node<V>* child) { child->prev=child->next=child; child->parent=parent; parent->degree++; parent->child=_merge(parent->child,child); }

void _unMarkAndUnParentAll(node<V>* n) { if(n==NULL)return; node<V>* c=n; do { c->marked=false; c->parent=NULL; c=c->next; }while(c!=n); }

node<V>* _removeMinimum(node<V>* n) { _unMarkAndUnParentAll(n->child); if(n->next==n) { n=n->child; } else { n->next->prev=n->prev; n->prev->next=n->next; n=_merge(n->next,n->child); } if(n==NULL)return n; node<V>* trees[64]={NULL};

while(true) { if(trees[n->degree]!=NULL) { node<V>* t=trees[n->degree]; if(t==n)break; trees[n->degree]=NULL; if(n->value<t->value) { t->prev->next=t->next; t->next->prev=t->prev; _addChild(n,t); } else { t->prev->next=t->next; t->next->prev=t->prev; if(n->next==n) { t->next=t->prev=t; _addChild(t,n); n=t; } else { n->prev->next=t; n->next->prev=t; t->next=n->next; t->prev=n->prev; _addChild(t,n); n=t; } } continue; } else { trees[n->degree]=n; } n=n->next; } node<V>* min=n; do { if(n->value<min->value)min=n; n=n->next; } while(n!=n); return min; }

node<V>* _cut(node<V>* heap,node<V>* n) { if(n->next==n) { n->parent->child=NULL; } else { n->next->prev=n->prev; n->prev->next=n->next; n->parent->child=n->next; } n->next=n->prev=n; n->marked=false; return _merge(heap,n); }

node<V>* _decreaseKey(node<V>* heap,node<V>* n,V value) { if(n->value<value)return heap; n->value=value; if(n->value<n->parent->value) { heap=_cut(heap,n); node<V>* parent=n->parent; n->parent=NULL; while(parent!=NULL && parent->marked) { heap=_cut(heap,parent); n=parent; parent=n->parent; n->parent=NULL; } if(parent!=NULL && parent->parent!=NULL)parent->marked=true; } return heap; }

node<V>* _find(node<V>* heap,V value) { node<V>* n=heap; if(n==NULL)return NULL; do { if(n->value==value)return n; node<V>* ret=_find(n->child,value); if(ret)return ret; n=n->next; }while(n!=heap); return NULL; } }; </lang>