# 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) {
} 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;
}
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 }

func MakeHeap() *Heap { return &Heap{} }

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
}

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
}

func (h Heap) Minimum() (min Value, ok bool) {
if h.Node == nil {
return
}
return h.value, true
}

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
r = n
}
if c := h.child; c != nil {
c.parent = nil
r := c.next
for r != c {
n := r.next
r.parent = nil
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
}

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

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

## Julia

Translation of: Python
```module FibonacciHeaps

export FNode, FibonacciHeap, insert, extractmin, findmin, decreasekey, delete!
export Insert, MakeHeap, Minimum, ExtractMin, DecreaseKey, Delete
import 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::Bool
end
FNode(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)
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 nodelist
end

mutable struct FibonacciHeap
rootlist::Union{FNode, Nothing}
minnode::Union{FNode, Nothing}
nodecount::Int
FibonacciHeap() = new(nothing, nothing, 0)
end
MakeHeap() = 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) time
findmin(h::FibonacciHeap) = h.minnode
Minimum(H) = findmin(H)                                                  # Minimum(H)  for task

# extract (delete) the min node from the heap in O(log n) time
function 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 z
end
ExtractMin(H) = extractmin(H)                                            # ExtractMin(H)  for task

# insert new node into the unordered root list in O(1) time
function 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 n
end
Insert(H, x) = insert(H, x)                                              # Insert(H, x)  for task

# modify the data of some node in the heap in O(1) time
function 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)
end
if x.value < root.minnode.value
root.minnode = x
end
end
DecreaseKey(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 newh
end
Union(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 list
function 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 = false
end

# cascading cut of parent node to obtain good time bounds
z = y.parent
if z != nothing
if y.mark == false
y.mark = true
else
cut(root, y, z)
end
end
end

# combine root nodes of equal degree to consolidate the heap
# by creating a list of unordered binomial trees
function 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
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
end
end

# actual linking of one node to another in the root list
# while also updating the child linked list
function 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 = false
end

# merge a node with the doubly linked root list
function 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
end
end

# merge a node with the doubly linked child list of a root node
function 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
end
end

# remove a node from the doubly linked root list
function remove_from_root_list(root, node)
if node == root.rootlist
root.rootlist = node.right
end
node.left.right = node.right
node.right.left = node.left
end

# remove a node from the doubly linked child list
function 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.left
end

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
end
end
Delete(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
Made another heap 2.
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
}
}

fun <V: Comparable<V>> makeHeap() = FibonacciHeap<V>()

class FibonacciHeap<V: Comparable<V>>(var node: Node<V>? = null) {

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
}

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
}

fun minimum(): V? = this.node?.value

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
r = n
}
val c = this.node!!.child
if (c != null) {
c.parent = null
var rr = c.next!!
while (rr != c) {
val n = rr.next!!
rr.parent = null
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
}

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

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

func initHeap*[T]: Heap[T] = discard

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

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

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

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
root = node

var child = heap.node.child
if not child.isNil:
child.parent = nil
var root = child.next
while root != child:
let node = root.next
root.parent = nil
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)

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)

func delete*[T](heap: var Heap[T]; node: Node[T]) =

let parent = node.parent
if parent.isNil:
if node == heap.node:
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] =
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:"
heap.visualize()

echo "\nUnion:"
var heap2 = initHeap[string]()
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.
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.
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
```with javascript_semantics
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[res] = NULL
else
nodes = append(nodes,NULL)
res = length(nodes)
end if
return res
end function

procedure release_slot(integer n)
nodes[n] = freelist
freelist = n
end procedure

function 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] = single
end procedure

function is_null(integer n)
-- (helps with refcounts for pwa/p2js)
return nodes[n] == NULL
end function

function Insert(integer h, object v)
integer n = 0
sequence x = new_node()
x[VALUE] = v
if is_null(h) then
x[NEXT] = h
x[PREV] = h
nodes[h] = x
else
n = new_slot()
nodes[n] = deep_copy(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

function Union(integer h, h2)
if is_null(h) then
h = h2
elsif not is_null(h2) 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

function Minimum(integer h)
if is_null(h) 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

function ExtractMin(integer h)
if is_null(h) 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]
r = n
end while
integer c = nodes[h][CHILD]
if c != NULL then
nodes[c][PARENT] = NULL
r := nodes[c][NEXT]
while r != c do
n := nodes[r][NEXT]
nodes[r][PARENT] = NULL
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 if
end procedure

function 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 h
end function

function 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 h
end 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 while
end procedure

procedure Vis(integer h)
if is_null(h) 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)

object m = Minimum(h)[1]
printf(1,"\nMinimum:\n%v\n",{m})

printf(1,"\nExtractMin:\n")
-- add a couple more items to demonstrate parent-child linking that
-- happens on delete min.
{h} = Insert(h,"bat")
integer x
{h,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
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)
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
z = y.parent
if z is not None:
if y.mark is False:
y.mark = True
else:
self.cut(y, 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
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;
r = \$n ;
}
if defined (my \c = self.root.child ) {
c.parent = Nil;
r = c.next;
while not r ~~ c {
my \$n = r.next;
r.parent = Nil;
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
r = n
}
var c = _node.child
if (c) {
c.parent = null
var rr = c.next
while (rr != c) {
var n = rr.next
rr.parent = null
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
```