I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# 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.
 This page uses content from Wikipedia. The original article was at Fibonacci heap. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

• 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++

`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);	} 	void display() const {	// function code adapted from GO code just below C++		node<V>* p = heap;		if (p == NULL) {			cout << "The Heap is Empty" << endl;			return;		}		cout << "The root nodes of Heap are: " << endl;		_display_tree(heap, "");		cout << endl;	} 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;				t->prev->next=t->next;				t->next->prev=t->prev;				if(n->value<t->value) {					_addChild(n,t);				} else {					if(n->next==n) {						t->next=t->prev=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;		n->parent->degree--;		return _merge(heap,n);	} 	node<V>* _decreaseKey(node<V>* heap,node<V>* n,V value) {		if(n->value<value)return heap;		n->value=value;		node<V>* parent = n->parent;		if(parent != nullptr && n->value < parent->value) {			heap=_cut(heap,n);			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;			if (n->value < heap->value)heap = n;		}		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;	} 	void _display_tree(node<V>* n, string pre) const {		string pc = "│  ";		node<V>* x = n;		do {			if (x->next != n) {				cout << pre << "├─";			} else {				cout << pre << "└─";				pc = "   ";			}			if (x->child == nullptr) {				cout << "─" << x->value << endl;			} else {				cout << "┐" << x->value << endl;				_display_tree(x->child, pre + pc);			}			//		cout << endl;			x = x->next;		} while (x != n);	} }; /* * main() for testing constructor, getMinimum(), display(), removeMinimum(), decreaseKey(), isEmpty() */int main(int argc, char** argv) { 	FibonacciHeap<int> fh; 	fh.insert(23);	fh.insert(7);	fh.insert(21);	fh.insert(3);	fh.insert(17);	fh.insert(24);	fh.insert(18);	fh.insert(52);	fh.insert(38);	fh.insert(30);	fh.insert(26);	fh.insert(46);	node<int>* n = fh.insert(39);	node<int>* m = fh.insert(41);	fh.insert(35); 	cout << "Heap Minimum: " << fh.getMinimum() << endl;	cout << "The Heap is: " << endl; 	fh.display();	cout << "Heap Minimum Extracted: " << fh.removeMinimum() << endl;	fh.display(); 	cout << "de: " << n->getValue() << " para: 5" << endl;	fh.decreaseKey(n, 5); 	cout << "Heap Minimum: " << fh.getMinimum() << endl;	fh.display(); 	cout << "de: " << m->getValue() << " para: 2" << endl;	fh.decreaseKey(m, 2); 	while (!fh.isEmpty()) {		cout << "Heap Minimum Extracted: " << fh.removeMinimum() << endl;		fh.display();	} 	return 0;}  `

## Go

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 requirementfunc MakeHeap() *Heap { return &Heap{} } // task requirementfunc (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 requirementfunc (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 requirementfunc (h Heap) Minimum() (min Value, ok bool) {    if h.Node == nil {        return    }    return h.value, true} // task requirementfunc (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 requirementfunc (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 requirementfunc (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
```

## Julia

Translation of: Python
`module FibonacciHeaps export FNode, FibonacciHeap, insert, extractmin, findmin, decreasekey, delete!export Insert, MakeHeap, Minimum, ExtractMin, DecreaseKey, Deleteimport Base.print mutable struct FNode{T}    value::T    degree::Int    parent::Union{FNode, Nothing}    child::Union{FNode, Nothing}    left::Union{FNode, Nothing}    right::Union{FNode, Nothing}    mark::BoolendFNode(data::T) where T = FNode{T}(data, 0, nothing, nothing, nothing, nothing, false) # Get list of nodes attached to head (of a circular doubly linked list)function aslist(head::FNode)    nodelist, node, stop = FNode[], head, head    flag = false    while true        if node == stop            flag && break            flag = true        end        push!(nodelist, node)        node = node.right    end    return nodelistend mutable struct FibonacciHeap    rootlist::Union{FNode, Nothing}    minnode::Union{FNode, Nothing}    nodecount::Int    FibonacciHeap() = new(nothing, nothing, 0)endMakeHeap() = FibonacciHeap()                                             # MakeHeap()  for task function print(io::IO, h::FibonacciHeap)    if h.rootlist == nothing        println("<empty heap>")        return    end    function printtree(io::IO, rootnode, s::String="")        n = rootnode        stem= "│ "        while n != nothing            if n.right != rootnode                print(io, s, "├─")            else                print(io, s, "└─")                stem = "  "            end            if n.child == nothing                println(io, "╴", n.value)            else                println(io, "┐", n.value)                printtree(io, n.child, s * stem)            end            if n.right == rootnode                break            end            n = n.right        end    end    printtree(io, h.rootlist)end  # return min node in O(1) timefindmin(h::FibonacciHeap) = h.minnodeMinimum(H) = findmin(H)                                                  # Minimum(H)  for task # extract (delete) the min node from the heap in O(log n) timefunction extractmin(root::FibonacciHeap)    z = root.minnode    if z != nothing        if z.child != nothing            # attach child nodes to root list            children = aslist(z.child)            for c in children                merge_with_root_list(root, c)                c.parent = nothing            end        end        remove_from_root_list(root, z)        # set new min node in heap        if z == z.right            root.minnode = root.rootlist = nothing        else            root.minnode = z.right            consolidate(root)        end        root.nodecount -= 1    end    return zendExtractMin(H) = extractmin(H)                                            # ExtractMin(H)  for task # insert new node into the unordered root list in O(1) timefunction insert(root, data)    n = FNode(data)    n.left = n.right = n    merge_with_root_list(root, n)    if root.minnode == nothing || n.value < root.minnode.value        root.minnode = n    end    root.nodecount += 1    return nendInsert(H, x) = insert(H, x)                                              # Insert(H, x)  for task # modify the data of some node in the heap in O(1) timefunction decreasekey(root, x, k)    if k > x.value        return nothing    end    x.value = k    y = x.parent    if y != nothing && x.value < y.value        cut(root, x, y)        cascadingcut(root, y)    end    if x.value < root.minnode.value        root.minnode = x    endendDecreaseKey(H, x, k) = decreasekey(H, x, k)                              # DecreaseKey(H, x, k) # 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)function merge(h1, h2)    newh = FibonacciHeap()    newh.rootlist, newh.minnode = h1.rootlist, h1.minnode    # fix pointers when merging the two heaps    last = h2.rootlist.left    h2.rootlist.left = newh.rootlist.left    newh.rootlist.left.right = h2.rootlist    newh.rootlist.left = last    newh.rootlist.left.right = newh.rootlist    # update min node if needed    if h2.minnode.value < newh.minnode.value        newh.min_node = h2.minnode    end    # update total nodes    newh.nodecount = h1.nodecount + h2.nodecount    return newhendUnion(H1, H2) = merge(H1, H2)   # NB: Union is a type in Julia          # Union(H1, H2)  for task # if a child node becomes smaller than its parent node we# cut this child node off and bring it up to the root listfunction cut(root, x, y)    remove_from_child_list(root, y, x)    y.degree -= 1    merge_with_root_list(root, x)    x.parent = nothing    x.mark = falseend # cascading cut of parent node to obtain good time boundsfunction cascadingcut(root, y)    z = y.parent    if z != nothing        if y.mark == false            y.mark = true        else            cut(root, y, z)            cascadingcut(root, z)        end    endend # combine root nodes of equal degree to consolidate the heap# by creating a list of unordered binomial treesfunction consolidate(root)    nodes = aslist(root.rootlist)    len = length(nodes)    A = fill!(Vector{Union{FNode, Nothing}}(undef, Int(round(log(root.nodecount)) * 2)), nothing)    for x in nodes        d = x.degree + 1        while A[d] != nothing            y = A[d]            if x.value > y.value                x, y = y, x            end            heaplink(root, y, x)            A[d] = nothing            d += 1        end        A[d] = x    end    # 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 nod in A        if nod != nothing && nod.value < root.minnode.value            root.minnode = nod        end    endend # actual linking of one node to another in the root list# while also updating the child linked listfunction heaplink(root, y, x)    remove_from_root_list(root, y)    y.left = y.right = y    merge_with_child_list(root, x, y)    x.degree += 1    y.parent = x    y.mark = falseend # merge a node with the doubly linked root listfunction merge_with_root_list(root, node)    if root.rootlist == nothing        root.rootlist = node    else        node.right = root.rootlist.right        node.left = root.rootlist        root.rootlist.right.left = node        root.rootlist.right = node    endend # merge a node with the doubly linked child list of a root nodefunction merge_with_child_list(root, parent, node)    if parent.child == nothing        parent.child = node    else        node.right = parent.child.right        node.left = parent.child        parent.child.right.left = node        parent.child.right = node    endend # remove a node from the doubly linked root listfunction remove_from_root_list(root, node)    if node == root.rootlist        root.rootlist = node.right    end    node.left.right = node.right    node.right.left = node.leftend # remove a node from the doubly linked child listfunction remove_from_child_list(root, parent, node)    if parent.child == parent.child.right        parent.child = nothing    elseif parent.child == node        parent.child = node.right        node.right.parent = parent    end    node.left.right = node.right    node.right.left = node.leftend function delete!(root, node)    if (parent = node.parent) == nothing        if node.child != nothing            cut(root, node.child, node)        end        remove_from_root_list(root, node)    else        remove_from_child_list(root, parent, node)    end    if root.rootlist != nothing        root.nodecount -= 1        root.minnode = root.rootlist        for n in aslist(root.rootlist)            if n != nothing && n.value < root.minnode.value                root.minnode = n            end        end    endendDelete(H, x) = delete!(H, x)                                             # Delete(H, x)   for task end  # module using .FibonacciHeaps const h1 = MakeHeap()println("Made heap 1:"), print(h1)Insert(h1, "now")println("Inserted the word now into heap 1"), print(h1)const h2 = MakeHeap()println("Made another heap 2.")const t = Insert(h2, "time")println("Inserted the word time into heap 2:"), print(h2)const h3 = Union(h1, h2)println("Made heap 3, union of heap 1 and heap 2:"), print(h3)println("The minimum of h3 is now \"\$(Minimum(h3).value)\".")const xkeys = [Insert(h3, x) for x in  ["all", "good", "men"]]println("Inserted 3 more into h3:"), print(h3)println("The minimum of h3 is now \"\$(Minimum(h3).value)\".")println("The extracted min from heap 3 is: ", ExtractMin(h3).value)println("h3 is now:"), print(h3)println("Decrease key of heap 3 value \$(xkeys[3].value) with the word come:")DecreaseKey(h3, xkeys[3], "come")print(h3)println("Delete node with value \$(xkeys[3].value) from heap 3:")Delete(h3, xkeys[3])print(h3)println("The minimum of h3 is now: ", Minimum(h3).value `
Output:
```Made heap 1:
<empty heap>
Inserted the word now into heap 1
└─╴now
Inserted the word time into heap 2:
└─╴time
Made heap 3, union of heap 1 and heap 2:
├─╴now
└─╴time
The minimum of h3 is now "now".
Inserted 3 more into h3:
├─╴now
├─╴men
├─╴good
├─╴all
└─╴time
The minimum of h3 is now "all".
The extracted min from heap 3 is: all
h3 is now:
└─┐good
├─╴time
└─┐men
└─╴now
Decrease key of heap 3 value men with the word come:
├─┐good
│ └─╴time
└─┐come
└─╴now
Delete node with value come from heap 3:
├─┐good
│ └─╴time
└─╴now
The minimum of h3 is now: good
```

## Kotlin

Translation of: Go
`// 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 requirementfun <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()}`
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
```

## Nim

Translation of: Go & Kotlin
`import strutils, tables type   Node*[T] = ref object    value: T    parent: Node[T]    child: Node[T]    prev, next: Node[T]    rank: int    mark: bool   Heap*[T] = object    node: Node[T]  func meld1[T](list, single: Node[T]) =  list.prev.next = single  single.prev = list.prev  single.next = list  list.prev = single  func meld2[T](a, b: Node[T]) =  a.prev.next = b  b.prev.next = a  swap a.prev, b.prev  # Task requirement.func initHeap*[T]: Heap[T] = discard  # Task requirement.func insert*[T](heap: var Heap[T]; value: T): Node[T] =  result = Node[T](value: value)  if heap.node.isNil:    result.next = result    result.prev = result    heap.node = result  else:    heap.node.meld1(result)    if result.value < heap.node.value:      heap.node = result  # Task requirement.func union*[T](heap1: var Heap[T]; heap2: var Heap[T]) =  if heap1.node.isNil:    heap1 = heap2  elif not heap2.node.isNil:    meld2(heap1.node, heap2.node)    if heap2.node.value < heap1.node.value:      heap1 = heap2  heap2.node = nil  # Task requirement.func min*[T](heap: Heap[T]): T =  if heap.node.isNil:    raise newException(ValueError, "cannot find minimum value in an empty heap.")  result = heap.node.value  func add[T](roots: var Table[int, Node[T]]; root: Node[T]) =  root.prev = root  root.next = root  var root = root  while true:    if root.rank notin roots: break    var node = roots.getOrDefault(root.rank, nil)    if node.isNil: break    roots.del(root.rank)    if node.value < root.value: swap node, root    node.parent = root    node.mark = false    if root.child.isNil:      node.next = node      node.prev = node      root.child = node    else:      meld1(root.child, node)    inc root.rank  roots[root.rank] = root  proc firstKey[T1, T2](t: Table[T1, T2]): T1 =  for key in t.keys: return key  # Task requirement.func extractMin*[T](heap: var Heap[T]): T =  let m = min(heap)  var roots: Table[int, Node[T]]   var root = heap.node.next  while root != heap.node:    let node = root.next    roots.add root    root = node   var child = heap.node.child  if not child.isNil:    child.parent = nil    var root = child.next    roots.add child    while root != child:      let node = root.next      root.parent = nil      roots.add root      root = node   if roots.len == 0:    heap.node = nil    return m   let key = roots.firstKey()  var node = roots[key]  roots.del(key)  node.next = node  node.prev = node  for root in roots.values:    root.prev = node    root.next = node.next    node.next.prev = root    node.next = root    if root.value < node.value: node = root  heap.node = node  result = m  # Forward reference.func cutAndMeld[T](heap: Heap[T]; node: Node[T])  func cut[T](heap: Heap[T]; node: Node[T]) =  let parent = node.parent  dec parent.rank  if parent.rank == 0:    parent.child = nil  else:    parent.child = node.next    node.prev.next = node.next    node.next.prev = node.prev  if parent.parent.isNil: return  if parent.mark:    heap.cutAndMeld(parent)  else:    parent.mark = true  func cutAndMeld[T](heap: Heap[T]; node: Node[T]) =  heap.cut(node)  node.parent = nil  meld1(heap.node, node)  # Task requirement.func decreaseKey*[T](heap: var Heap[T]; node: Node[T]; val: T) =  if node.value < val:    raise newException(ValueError, "“decreaseKey” new value greater than existing value.")   node.value = val  if node == heap.node: return   if node.parent.isNil:    if val < heap.node.value:      heap.node = node  else:    heap.cutAndMeld(node)  # Task requirement.func delete*[T](heap: var Heap[T]; node: Node[T]) =   let parent = node.parent  if parent.isNil:    if node == heap.node:      discard heap.extractMin()      return    node.prev.next = node.next    node.next.prev = node.prev  else:    heap.cut(node)   var child = node.child  if child.isNil: return   while true:    child.parent = nil    child = child.next    if child == node.child: break   meld2(heap.node, child)  iterator nodes[T](head: Node[T]): Node[T] =  if not head.isNil:    yield head    var node = head.next    while node != head:      yield node      node = node.next  proc visualize[T](heap: Heap[T]) =   if heap.node.isNil:    echo "<empty>"    return   proc print[T](node: Node[T]; pre: string) =    var pc = "│ "    for curr in node.nodes():      if curr.next != node:        stdout.write pre, "├─"      else:        stdout.write pre, "└─"        pc = "  "      if curr.child.isNil:        echo "╴", curr.value      else:        echo "┐", curr.value        print(curr.child, pre & pc)   print(heap.node, "")  when isMainModule:   echo "MakeHeap:"  var heap = initHeap[string]()  heap.visualize()   echo "\nInsert:"  discard heap.insert("cat")  heap.visualize()   echo "\nUnion:"  var heap2 = initHeap[string]()  discard heap2.insert("rat")  heap.union(heap2)  heap.visualize()   echo "\nMinimum:"  var m = min(heap)  echo m   echo "\nExtractMin:"  # Add a couple more items to demonstrate parent-child linking that happens on delete min.  discard heap.insert("bat")  let node = heap.insert("meerkat")  # Save node for decrease key and delete demos.  m = heap.extractMin()  echo "(extracted \$#)" % m  heap.visualize()   echo "\nDecreaseKey:"  heap.decreaseKey(node, "gnat")  heap.visualize()   echo "\nDelete:"  # Add a couple more items.  discard heap.insert("bobcat")  discard heap.insert("bat")  echo "(deleting \$#)" % node.value  heap.delete(node)  heap.visualize()`
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```

## Phix

Translation of: Go
`enum VALUE, PARENT, CHILD, PREV, NEXT, RANK, MARK, NODELEN=\$ function new_node()    return repeat(NULL,NODELEN)end function sequence nodes = {}integer freelist = NULL function new_slot()    integer res    if freelist!=NULL then        res = freelist        freelist = nodes[freelist]        nodes[freelist] = NULL    else        nodes = append(nodes,NULL)        res = length(nodes)    end if    return resend function procedure release_slot(integer n)    nodes[n] = freelist    freelist = nend procedure -- task requirementfunction MakeHeap()    return new_slot()end function procedure meld1(integer list, single)    nodes[nodes[list][PREV]][NEXT] = single    nodes[single][PREV] = nodes[list][PREV]    nodes[single][NEXT] = list    nodes[list][PREV] = singleend procedure -- task requirementfunction Insert(integer h, object v)    integer n = 0    sequence x = new_node()    x[VALUE] = v    if nodes[h] == NULL then        x[NEXT] = h        x[PREV] = h        nodes[h] = x    else        n = new_slot()        nodes[n] = x        meld1(h, n)        if nodes[n][VALUE]<nodes[h][VALUE] then            h = n        end if    end if    return {h,n}end function procedure meld2(integer a, b)    nodes[nodes[a][PREV]][NEXT] = b    nodes[nodes[b][PREV]][NEXT] = a    {nodes[a][PREV], nodes[b][PREV]} = {nodes[b][PREV], nodes[a][PREV]}end procedure -- task requirementfunction Union(integer h, h2)    if nodes[h] == NULL then        h = h2    elsif nodes[h2] != NULL then        meld2(h, h2)        if nodes[h2][VALUE]<nodes[h][VALUE] then            h = h2        end if    else        release_slot(h2)    end if    return {h,NULL} -- (h2:=NULL implied)end function -- task requirementfunction Minimum(integer h)    if nodes[h] == NULL then        return {"<none>",false}    end if    return {nodes[h][VALUE], true}end function procedure add_roots(integer r, integer roots)    nodes[r][PREV] = r    nodes[r][NEXT] = r    while true do        integer node = getd_index(nodes[r][RANK],roots)        if node=NULL then exit end if        integer x = getd_by_index(node,roots)        deld(nodes[r][RANK],roots)        if nodes[x][VALUE]<nodes[r][VALUE] then            {r, x} = {x, r}        end if        nodes[x][PARENT] = r        nodes[x][MARK] = false        if nodes[r][CHILD] == NULL then            nodes[x][NEXT] = x            nodes[x][PREV] = x            nodes[r][CHILD] = x        else            meld1(nodes[r][CHILD], x)        end if        nodes[r][RANK] += 1    end while    setd(nodes[r][RANK],r,roots)end procedure -- task requirementfunction ExtractMin(integer h)    if nodes[h] == NULL then        return {h,"<none>",false}    end if    object minimum = nodes[h][VALUE]    integer roots = new_dict()    integer r = nodes[h][NEXT], n    while r != h do        n := nodes[r][NEXT]        add_roots(r,roots)        r = n    end while    integer c = nodes[h][CHILD]    if c != NULL then        nodes[c][PARENT] = NULL        r := nodes[c][NEXT]        add_roots(c,roots)        while r != c do            n := nodes[r][NEXT]            nodes[r][PARENT] = NULL            add_roots(r,roots)            r = n        end while    end if    if dict_size(roots) == 0 then        destroy_dict(roots)        return {NULL, minimum, true}    end if    integer d = getd_partial_key(0,roots)    integer mv = getd(d,roots)    deld(d,roots)    nodes[mv][NEXT] = mv    nodes[mv][PREV] = mv    sequence rs = getd_all_keys(roots)    for i=1 to length(rs) do        r = getd(rs[i],roots)        nodes[r][PREV] = mv        nodes[r][NEXT] = nodes[mv][NEXT]        nodes[nodes[mv][NEXT]][PREV] = r        nodes[mv][NEXT] = r        if nodes[r][VALUE]<nodes[mv][VALUE] then            mv = r        end if    end for    h = mv    destroy_dict(roots)    return {h, minimum, true}end function procedure cut_and_meld(integer h, x, bool meld)    integer p := nodes[x][PARENT]    nodes[p][RANK] -= 1    if nodes[p][RANK] == 0 then        nodes[p][CHILD] = NULL    else        nodes[p][CHILD] = nodes[x][NEXT]        nodes[nodes[x][PREV]][NEXT] = nodes[x][NEXT]        nodes[nodes[x][NEXT]][PREV] = nodes[x][PREV]    end if    if nodes[p][PARENT] == NULL then        return    end if    if not nodes[p][MARK] then        nodes[p][MARK] = true        return    end if    cut_and_meld(h,p,true)    if meld then        nodes[x][PARENT] = NULL        meld1(h, x)    end ifend procedure -- task requirementfunction DecreaseKey(integer h, n, object v)    if nodes[n][VALUE]<v then        crash("DecreaseKey new value greater than existing value")    end if    nodes[n][VALUE] = v    if n!=h then        integer p := nodes[n][PARENT]        if p == NULL then            if v<nodes[h][VALUE] then                h = n            end if        else            cut_and_meld(h,n,true)        end if    end if    return hend function -- task requirementfunction Delete(integer h, n)    integer p := nodes[n][PARENT]    if p == NULL then        if n == h then            {h} = ExtractMin(h)            return h        end if        nodes[nodes[n][PREV]][NEXT] = nodes[n][NEXT]        nodes[nodes[n][NEXT]][PREV] = nodes[n][PREV]    else        cut_and_meld(h,n,false)    end if    integer c := nodes[n][CHILD]    if c != NULL then        while true do            nodes[c][PARENT] = NULL            c = nodes[c][NEXT]            if c == nodes[n][CHILD] then                exit            end if        end while        meld2(h, c)    end if    return hend function constant W=platform()=WINDOWS,         Horizontal = iff(W?#C4:'-'),         Vertical   = iff(W?#B3:'|'),         sBtmLeft   = iff(W?#C0:'+'),         sLeftTee   = iff(W?#C3:'+'),         sTopRight  = iff(W?#BF:'+') procedure vis(integer n, string pre)    string pc = Vertical&" "    sequence x = nodes[n]    while true do        integer next = x[NEXT]        if next!=n then            printf(1,pre&sLeftTee&Horizontal)        else            printf(1,pre&sBtmLeft&Horizontal)            pc = "  "        end if        if x[CHILD] == NULL then            printf(1,"%c %s\n",{Horizontal,sprint(x[VALUE])})        else            printf(1,"%c %s\n",{sTopRight,sprint(x[VALUE])})            vis(x[CHILD], pre&pc)        end if        if next=n then exit end if        x = nodes[next]    end whileend procedure procedure Vis(integer h)    if nodes[h] == NULL then        printf(1,"<empty>\n")        return    end if    vis(h,"")end procedure printf(1,"MakeHeap:\n")integer h := MakeHeap()Vis(h) printf(1,"\nInsert:\n"){h} = Insert(h,"cat")Vis(h) printf(1,"\nUnion:\n")integer h2 := MakeHeap(){h2} = Insert(h2,"rat"){h,h2} = Union(h,h2)     -- (h2:=NULL)Vis(h) printf(1,"\nMinimum:\n"){object m, {}} = Minimum(h)?m printf(1,"\nExtractMin:\n")-- add a couple more items to demonstrate parent-child linking that-- happens on delete min.{h} = Insert(h,"bat"){h,integer x} = Insert(h,"meerkat") -- save x for decrease key and delete demos{h,m,{}} = ExtractMin(h)printf(1,"(extracted %s)\n", {sprint(m)})Vis(h) printf(1,"\nDecreaseKey:\n")h = DecreaseKey(h, x, "gnat")Vis(h) printf(1,"\nDelete:\n")-- add yet a couple more items to show how F&T's original delete was-- lazier than CLRS's delete.{h} = Insert(h,"bobcat"){h} = Insert(h,"bat")printf(1,"(deleting %s)\n", {sprint(nodes[x][VALUE])})h = Delete(h,x)Vis(h)`
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

`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`

## Raku

Translation of: Go & Kotlin
`# 20200609 Raku programming solution subset vEle of Any;  class Node {   has vEle \$.value  is rw is default(Nil) ;    has Node \$.parent is rw ;   has Node \$.child  is rw ;    has Node \$.prev   is rw ;    has Node \$.next   is rw ;     has Int  \$.rank   is rw is default(0) ;    has Bool \$.mark   is rw is default(False) ; } multi infix:<⪡>(vEle \a, vEle \b) { a le b } # custom defined 'less than' class Heap {     has Node \$.root is rw ;      method MakeHeap { self.root = Node.new }     method Insert(vEle \v) {      my \$x = Node.new: value => v;      if self.root.value ~~ Nil {         \$x.next = \$x;         \$x.prev = \$x;          self.root = \$x      } else {         meld1(self.root, \$x);         self.root = \$x if \$x.value ⪡ self.root.value       }      return \$x   }    method Union(Heap \$h2) {      if not self.root.defined {         self.root = \$h2.root      } elsif \$h2.root.defined { 		          meld2(self.root, \$h2.root);         self.root = \$h2.root if \$h2.root.value ⪡ self.root.value       }      \$h2.root = Nil;   }    method Minimum() {      return unless self.root.defined;       return self.root.value   }    method ExtractMin() {      return Nil unless self.root.defined;      my \min = self.root.value;      my %roots;       sub add (Node \r) {         r.prev = r;         r.next = r;         loop {            (defined my \x = %roots{r.rank}) or last;            %roots{r.rank}:delete;            (r, x) = (x, r) if x.value ⪡ r.value ;             x.parent = r ;            x.mark = False ;            if not r.child.defined {               x.next = x;               x.prev = x;               r.child = x            } else {               meld1(r.child, x)            }            r.rank++         }         %roots{r.rank} = r ;      }       loop (my \r = self.root.next ; not r ~~ self.root ; ) {         my \$n = r.next;                  add(r);         r = \$n ;      }      if defined (my \c = self.root.child ) {         c.parent = Nil;         r = c.next;         add(c);         while not r ~~ c {            my \$n = r.next;            r.parent = Nil;            add(r);            r = \$n;         }      }       unless %roots.defined {         self.root = Nil;         return min      }      my Node \$mv = %roots{my \$d = %roots.keys.first};       %roots{\$d}:delete;      \$mv.next = \$mv;      \$mv.prev = \$mv;      %roots.values.map: {         \$_.prev = \$mv;         \$_.next = \$mv.next;         \$mv.next.prev = \$_;         \$mv.next = \$_;          \$mv = \$_ if \$_.value ⪡ \$mv.value       }      self.root = \$mv;      return min   }     method DecreaseKey(\n, \v) {      die "DecreaseKey new value greater than existing value" if n.value ⪡ v;      n.value = v;       return Nil if n ~~ self.root;      my \p = n.parent;      unless p.defined {         self.root = n if v ⪡ self.root.value;          return Nil       }      self.cutAndMeld(n);      return Nil    }    method cutAndMeld(\x) {      self.cut(x);      x.parent = Nil;      meld1(self.root, x)   }    method cut(\x) {      my \p = x.parent;      return Nil unless p.defined;      p.rank--;      if p.rank == 0 {         p.child = Nil      } else {         p.child = x.next;         x.prev.next = x.next;         x.next.prev = x.prev      }      return Nil unless p.parent.defined;      unless p.mark {        p.mark = True;        return Nil      }      self.cutAndMeld(p)   }    method Delete(\n) {      my \p = n.parent;      if not p.defined {         self.ExtractMin() and return if n ~~ self.root ;          n.prev.next = n.next;         n.next.prev = n.prev      } else {         self.cut(n)      }      my \c = n.child;      return Nil unless c.defined;      loop ( c.parent = Nil, c = c.next ; c ~~ n.child ; c = c.next ) {}       meld2(self.root, c)   }    method Vis() {       if self.root.value ~~ Nil { say "<empty>" and return }       sub f(Node \$n, Str \$pre) {         loop ( my \$pc = "│ ", my \$x = \$n ; ; \$x = \$x.next) {            if !(\$x.next ~~ \$n) {               print \$pre, "├─"            } else {               print \$pre, "└─";               \$pc = "  "            }            if not \$x.child.defined {               say "╴", \$x.value            } else {               say "┐", \$x.value;               f(\$x.child, \$pre~\$pc)            }            last if \$x.next ~~ \$n          }      }      f(self.root, "")   }} sub meld1(\list, \single) {   list.prev.next = single;   single.prev = list.prev;   single.next = list;   list.prev = single;} sub meld2(\a, \b) {   a.prev.next = b;   b.prev.next = a;   ( a.prev, b.prev ) = ( b.prev, a.prev )} say "MakeHeap:";my \$h = Heap.new; \$h.MakeHeap;\$h.Vis; say "\nInsert:";\$h.Insert("cat");\$h.Vis; say "\nUnion:";my \$h2 = Heap.new; \$h2.MakeHeap;\$h2.Insert("rat");\$h.Union(\$h2);\$h.Vis; say "\nMinimum:";my \m = \$h.Minimum();say m; say "\nExtractMin:";\$h.Insert("bat");my \$x = \$h.Insert("meerkat"); say "extracted: ", my \$mm = \$h.ExtractMin();\$h.Vis; say "\nDecreaseKey:";\$h.DecreaseKey(\$x, "gnat");\$h.Vis; say "\nDelete:";\$h.Insert("bobcat");\$h.Insert("bat");say "deleting: ", \$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```

## Wren

Translation of: Kotlin
Library: Wren-str

This just deals with nodes whose values are strings.

`import "/str" for Str class Node {    construct new(value) {        _value  = value        _parent = null        _child  = null        _prev   = null        _next   = null        _rank   = 0        _mark   = false    }     value  { _value  }    parent { _parent }    child  { _child  }    prev   { _prev   }    next   { _next   }    rank   { _rank   }    mark   { _mark   }     value=(v)  { _value = v  }    parent=(p) { _parent = p }    child=(c)  { _child = c  }    prev=(p)   { _prev = p   }    next=(n)   { _next = n   }    rank=(r)   { _rank = r   }    mark=(m)   { _mark = m   }     meld1(node) {        if (_prev) _prev.next = node        node.prev = _prev        node.next = this        _prev = node    }     meld2(node) {        if (_prev) _prev.next = node        if (node.prev) node.prev.next = this        var temp = _prev        _prev = node.prev        node.prev = temp    }} class FibonacciHeap {    construct new() {        _node = null    }     construct new(node) {        _node = node    }     node     { _node }    node=(n) { _node = n }     insert(v) {        var x = Node.new(v)        if (!_node) {            x.next = x            x.prev = x            _node = x        } else {            _node.meld1(x)            if (Str.lt(x.value, _node.value)) _node = x        }        return x    }     union(other) {        if (!_node) {            _node = other.node        } else if (other.node) {            _node.meld2(other.node)            if (Str.lt(other.node.value, _node.value)) _node = other.node        }        other.node = null    }     minimum() { _node.value }     extractMin() {        if (!_node) return null        var min = minimum()        var roots = {}         var add = Fn.new { |r|            r.prev = r            r.next = r            var rr = r            while (true) {                var x = roots[rr.rank]                if (!x) break                roots.remove(rr.rank)                if (Str.lt(x.value, rr.value)) {                    var t = rr                    rr = x                    x = t                }                x.parent = rr                x.mark = false                if (!rr.child) {                    x.next = x                    x.prev = x                    rr.child = x                } else {                    rr.child.meld1(x)                }                rr.rank = rr.rank + 1            }            roots[rr.rank] = rr        }         var r = _node.next        while (r != _node) {            var n = r.next            add.call(r)            r = n        }        var c = _node.child        if (c) {            c.parent = null            var rr = c.next            add.call(c)            while (rr != c) {                var n = rr.next                rr.parent = null                add.call(rr)                rr = n            }        }        if (roots.isEmpty) {            _node = null            return min        }        var d = roots.keys.toList[0]        var mv = roots[d]        roots.remove(d)        mv.next = mv        mv.prev = mv        for (rr in roots.values) {            rr.prev = mv            rr.next = mv.next            mv.next.prev = rr            mv.next = rr            if (Str.lt(rr.value, mv.value)) mv = rr        }        _node = mv        return min    }     decreaseKey(n, v) {        if (Str.le(n.value, v)) {            Fiber.abort("In 'decreaseKey' new value greater than or equal to existing value.")        }        n.value = v        if (n == _node) return        var p = n.parent        if (!p) {            if (Str.lt(v, _node.value)) _node = n            return        }        cutAndMeld_(n)    }     cut_(x) {        var p = x.parent        if (!p) return        p.rank = p.rank - 1        if (p.rank == 0) {             p.child = null        } else {            p.child = x.next            if (x.prev) x.prev.next = x.next            if (x.next) x.next.prev = x.prev        }        if (!p.parent) return        if (!p.mark) {            p.mark = true            return        }        cutAndMeld_(p)    }     cutAndMeld_(x) {        cut_(x)        x.parent = null        if(_node) _node.meld1(x)    }     delete(n) {        var p = n.parent        if (!p) {            if (n == _node) {                extractMin()                return            }            if (n.prev) n.prev.next = n.next            if (n.next) n.next.prev = n.prev        } else {            cut_(n)        }        var c = n.child        if (!c) return        while (true) {            c.parent = null            c = c.next            if (c == n.child) break        }        if (_node) _node.meld2(c)    }     visualize() {        if (!_node) {            System.print("<empty>")            return        }         var f // recursive closure        f = Fn.new { |n, pre|            var pc = "│ "            var x = n            while (true) {                if (x.next != n) {                    System.write("%(pre)├─")                } else {                    System.write("%(pre)└─")                    pc = "  "                }                if (!x.child) {                    System.print("╴ %(x.value)")                } else {                    System.print("┐ %(x.value)")                    f.call(x.child, pre + pc)                }                if (x.next == n) break                x = x.next            }        }        f.call(_node, "")    }} var makeHeap = Fn.new { FibonacciHeap.new() } System.print("MakeHeap:")var h = makeHeap.call()h.visualize() System.print("\nInsert:")h.insert("cat")h.visualize() System.print("\nUnion:")var h2 = makeHeap.call()h2.insert("rat")h.union(h2)h.visualize() System.print("\nMinimum:")var m = h.minimum()System.print(m) System.print("\nExtractMin:")// add a couple more items to demonstrate parent-child linking that// happens on delete min.h.insert("bat")var x = h.insert("meerkat")  // save x for decrease key and delete demos.m = h.extractMin()System.print("(extracted '%(m)')")h.visualize() System.print("\nDecreaseKey:")h.decreaseKey(x, "gnat")h.visualize() System.print("\nDelete:")// add a couple more items.h.insert("bobcat")h.insert("bat")System.print("(deleting '%(x.value)')")h.delete(x)h.visualize()`
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
```