Fibonacci heap

From Rosetta Code
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[edit]

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

C++[edit]

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;
}
};

Go[edit]

A package. Implementation follows Fredman and Tarjan's 1987 paper.

package fib
 
import "fmt"
 
type Value interface {
LT(Value) bool
}
 
type Node struct {
value Value
parent *Node
child *Node
prev, next *Node
rank int
mark bool
}
 
func (n Node) Value() Value { return n.value }
 
type Heap struct{ *Node }
 
// task requirement
func MakeHeap() *Heap { return &Heap{} }
 
// task requirement
func (h *Heap) Insert(v Value) *Node {
x := &Node{value: v}
if h.Node == nil {
x.next = x
x.prev = x
h.Node = x
} else {
meld1(h.Node, x)
if x.value.LT(h.value) {
h.Node = x
}
}
return x
}
 
func meld1(list, single *Node) {
list.prev.next = single
single.prev = list.prev
single.next = list
list.prev = single
}
 
// task requirement
func (h *Heap) Union(h2 *Heap) {
switch {
case h.Node == nil:
*h = *h2
case h2.Node != nil:
meld2(h.Node, h2.Node)
if h2.value.LT(h.value) {
*h = *h2
}
}
h2.Node = nil
}
 
func meld2(a, b *Node) {
a.prev.next = b
b.prev.next = a
a.prev, b.prev = b.prev, a.prev
}
 
// task requirement
func (h Heap) Minimum() (min Value, ok bool) {
if h.Node == nil {
return
}
return h.value, true
}
 
// task requirement
func (h *Heap) ExtractMin() (min Value, ok bool) {
if h.Node == nil {
return
}
min = h.value
roots := map[int]*Node{}
add := func(r *Node) {
r.prev = r
r.next = r
for {
x, ok := roots[r.rank]
if !ok {
break
}
delete(roots, r.rank)
if x.value.LT(r.value) {
r, x = x, r
}
x.parent = r
x.mark = false
if r.child == nil {
x.next = x
x.prev = x
r.child = x
} else {
meld1(r.child, x)
}
r.rank++
}
roots[r.rank] = r
}
for r := h.next; r != h.Node; {
n := r.next
add(r)
r = n
}
if c := h.child; c != nil {
c.parent = nil
r := c.next
add(c)
for r != c {
n := r.next
r.parent = nil
add(r)
r = n
}
}
if len(roots) == 0 {
h.Node = nil
return min, true
}
var mv *Node
var d int
for d, mv = range roots {
break
}
delete(roots, d)
mv.next = mv
mv.prev = mv
for _, r := range roots {
r.prev = mv
r.next = mv.next
mv.next.prev = r
mv.next = r
if r.value.LT(mv.value) {
mv = r
}
}
h.Node = mv
return min, true
}
 
// task requirement
func (h *Heap) DecreaseKey(n *Node, v Value) error {
if n.value.LT(v) {
return fmt.Errorf("DecreaseKey new value greater than existing value")
}
n.value = v
if n == h.Node {
return nil
}
p := n.parent
if p == nil {
if v.LT(h.value) {
h.Node = n
}
return nil
}
h.cutAndMeld(n)
return nil
}
 
func (h Heap) cut(x *Node) {
p := x.parent
p.rank--
if p.rank == 0 {
p.child = nil
} else {
p.child = x.next
x.prev.next = x.next
x.next.prev = x.prev
}
if p.parent == nil {
return
}
if !p.mark {
p.mark = true
return
}
h.cutAndMeld(p)
}
 
func (h Heap) cutAndMeld(x *Node) {
h.cut(x)
x.parent = nil
meld1(h.Node, x)
}
 
// task requirement
func (h *Heap) Delete(n *Node) {
p := n.parent
if p == nil {
if n == h.Node {
h.ExtractMin()
return
}
n.prev.next = n.next
n.next.prev = n.prev
} else {
h.cut(n)
}
c := n.child
if c == nil {
return
}
for {
c.parent = nil
c = c.next
if c == n.child {
break
}
}
meld2(h.Node, c)
}
 
// adapted from task "Visualize a tree"
func (h Heap) Vis() {
if h.Node == nil {
fmt.Println("<empty>")
return
}
var f func(*Node, string)
f = func(n *Node, pre string) {
pc := "│ "
for x := n; ; x = x.next {
if x.next != n {
fmt.Print(pre, "├─")
} else {
fmt.Print(pre, "└─")
pc = " "
}
if x.child == nil {
fmt.Println("╴", x.value)
} else {
fmt.Println("┐", x.value)
f(x.child, pre+pc)
}
if x.next == n {
break
}
}
}
f(h.Node, "")
}

A demonstration:

package main
 
import (
"fmt"
 
"fib"
)
 
type str string
 
func (s str) LT(t fib.Value) bool { return s < t.(str) }
 
func main() {
fmt.Println("MakeHeap:")
h := fib.MakeHeap()
h.Vis()
 
fmt.Println("\nInsert:")
h.Insert(str("cat"))
h.Vis()
 
fmt.Println("\nUnion:")
h2 := fib.MakeHeap()
h2.Insert(str("rat"))
h.Union(h2)
h.Vis()
 
fmt.Println("\nMinimum:")
m, _ := h.Minimum()
fmt.Println(m)
 
fmt.Println("\nExtractMin:")
// add a couple more items to demonstrate parent-child linking that
// happens on delete min.
h.Insert(str("bat"))
x := h.Insert(str("meerkat")) // save x for decrease key and delete demos
m, _ = h.ExtractMin()
fmt.Printf("(extracted %v)\n", m)
h.Vis()
 
fmt.Println("\nDecreaseKey:")
h.DecreaseKey(x, str("gnat"))
h.Vis()
fmt.Println("\nDelete:")
// add yet a couple more items to show how F&T's original delete was
// lazier than CLRS's delete.
h.Insert(str("bobcat"))
h.Insert(str("bat"))
fmt.Printf("(deleting %v)\n", x.Value())
h.Delete(x)
h.Vis()
}
Output:
MakeHeap:
<empty>

Insert:
└─╴ cat

Union:
├─╴ cat
└─╴ rat

Minimum:
cat

ExtractMin:
(extracted bat)
├─┐ cat
│ └─╴ rat
└─╴ meerkat

DecreaseKey:
├─┐ cat
│ └─╴ rat
└─╴ gnat

Delete:
(deleting gnat)
├─╴ bat
├─╴ bobcat
└─┐ cat
  └─╴ rat

Python[edit]

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