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) - decrease value of element x in heap H to value k
- Delete(H,x) - remove element x from heap H
C++
<lang cpp>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>
Go
A package. Implementation follows Fredman and Tarjan's 1987 paper. <lang go>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, "")
}</lang> A demonstration: <lang go>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()
}</lang>
- 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
Kotlin
<lang scala>// version 1.2.21
class Node<V : Comparable<V>>(var value: V) {
var parent: Node<V>? = null var child: Node<V>? = null var prev: Node<V>? = null var next: Node<V>? = null var rank = 0 var mark = false
fun meld1(node: Node<V>) { this.prev?.next = node node.prev = this.prev node.next = this this.prev = node }
fun meld2(node: Node<V>) { this.prev?.next = node node.prev?.next = this val temp = this.prev this.prev = node.prev node.prev = temp }
}
// task requirement fun <V: Comparable<V>> makeHeap() = FibonacciHeap<V>()
class FibonacciHeap<V: Comparable<V>>(var node: Node<V>? = null) {
// task requirement fun insert(v: V): Node<V> { val x = Node(v) if (this.node == null) { x.next = x x.prev = x this.node = x } else { this.node!!.meld1(x) if (x.value < this.node!!.value) this.node = x } return x }
// task requirement fun union(other: FibonacciHeap<V>) { if (this.node == null) { this.node = other.node } else if (other.node != null) { this.node!!.meld2(other.node!!) if (other.node!!.value < this.node!!.value) this.node = other.node } other.node = null }
// task requirement fun minimum(): V? = this.node?.value
// task requirement fun extractMin(): V? { if (this.node == null) return null val min = minimum() val roots = mutableMapOf<Int, Node<V>>()
fun add(r: Node<V>) { r.prev = r r.next = r var rr = r while (true) { var x = roots[rr.rank] ?: break roots.remove(rr.rank) if (x.value < rr.value) { val t = rr rr = x x = t } x.parent = rr x.mark = false if (rr.child == null) { x.next = x x.prev = x rr.child = x } else { rr.child!!.meld1(x) } rr.rank++ } roots[rr.rank] = rr }
var r = this.node!!.next while (r != this.node) { val n = r!!.next add(r) r = n } val c = this.node!!.child if (c != null) { c.parent = null var rr = c.next!! add(c) while (rr != c) { val n = rr.next!! rr.parent = null add(rr) rr = n } } if (roots.isEmpty()) { this.node = null return min } val d = roots.keys.first() var mv = roots[d]!! roots.remove(d) mv.next = mv mv.prev = mv for ((_, rr) in roots) { rr.prev = mv rr.next = mv.next mv.next!!.prev = rr mv.next = rr if (rr.value < mv.value) mv = rr } this.node = mv return min }
// task requirement fun decreaseKey(n: Node<V>, v: V) { require (n.value > v) { "In 'decreaseKey' new value greater than existing value" } n.value = v if (n == this.node) return val p = n.parent if (p == null) { if (v < this.node!!.value) this.node = n return } cutAndMeld(n) }
private fun cut(x: Node<V>) { val p = x.parent if (p == null) return p.rank-- if (p.rank == 0) { p.child = null } else { p.child = x.next x.prev?.next = x.next x.next?.prev = x.prev } if (p.parent == null) return if (!p.mark) { p.mark = true return } cutAndMeld(p) }
private fun cutAndMeld(x: Node<V>) { cut(x) x.parent = null this.node?.meld1(x) }
// task requirement fun delete(n: Node<V>) { val p = n.parent if (p == null) { if (n == this.node) { extractMin() return } n.prev?.next = n.next n.next?.prev = n.prev } else { cut(n) } var c = n.child if (c == null) return while (true) { c!!.parent = null c = c.next if (c == n.child) break } this.node?.meld2(c!!) }
fun visualize() { if (this.node == null) { println("<empty>") return }
fun f(n: Node<V>, pre: String) { var pc = "│ " var x = n while (true) { if (x.next != n) { print("$pre├─") } else { print("$pre└─") pc = " " } if (x.child == null) { println("╴ ${x.value}") } else { println("┐ ${x.value}") f(x.child!!, pre + pc) } if (x.next == n) break x = x.next!! } } f(this.node!!, "") }
}
fun main(args: Array<String>) {
println("MakeHeap:") val h = makeHeap<String>() h.visualize()
println("\nInsert:") h.insert("cat") h.visualize()
println("\nUnion:") val h2 = makeHeap<String>() h2.insert("rat") h.union(h2) h.visualize()
println("\nMinimum:") var m = h.minimum() println(m)
println("\nExtractMin:") // add a couple more items to demonstrate parent-child linking that // happens on delete min. h.insert("bat") val x = h.insert("meerkat") // save x for decrease key and delete demos. m = h.extractMin() println("(extracted $m)") h.visualize()
println("\nDecreaseKey:") h.decreaseKey(x, "gnat") h.visualize()
println("\nDelete:") // add a couple more items. h.insert("bobcat") h.insert("bat") println("(deleting ${x.value})") h.delete(x) h.visualize()
}</lang>
- 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
<lang python>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>