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)

Task

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

C++

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

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

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

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

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

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

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

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

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

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

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

</lang>

Go

A package. Implementation follows Fredman and Tarjan's 1987 paper. <lang go>package fib

import "fmt"

type Value interface {

   LT(Value) bool

}

type Node struct {

   value      Value
   parent     *Node
   child      *Node
   prev, next *Node
   rank       int
   mark       bool

}

func (n Node) Value() Value { return n.value }

type Heap struct{ *Node }

// task requirement func MakeHeap() *Heap { return &Heap{} }

// task requirement func (h *Heap) Insert(v Value) *Node {

   x := &Node{value: v}
   if h.Node == nil {
       x.next = x
       x.prev = x
       h.Node = x
   } else {
       meld1(h.Node, x)
       if x.value.LT(h.value) {
           h.Node = x
       }
   }
   return x

}

func meld1(list, single *Node) {

   list.prev.next = single
   single.prev = list.prev
   single.next = list
   list.prev = single

}

// task requirement func (h *Heap) Union(h2 *Heap) {

   switch {
   case h.Node == nil:
       *h = *h2
   case h2.Node != nil:
       meld2(h.Node, h2.Node)
       if h2.value.LT(h.value) {
           *h = *h2
       }
   }
   h2.Node = nil

}

func meld2(a, b *Node) {

   a.prev.next = b
   b.prev.next = a
   a.prev, b.prev = b.prev, a.prev

}

// task requirement func (h Heap) Minimum() (min Value, ok bool) {

   if h.Node == nil {
       return
   }
   return h.value, true

}

// task requirement func (h *Heap) ExtractMin() (min Value, ok bool) {

   if h.Node == nil {
       return
   }
   min = h.value
   roots := map[int]*Node{}
   add := func(r *Node) {
       r.prev = r
       r.next = r
       for {
           x, ok := roots[r.rank]
           if !ok {
              break
           }
           delete(roots, r.rank)
           if x.value.LT(r.value) {
               r, x = x, r
           }
           x.parent = r
           x.mark = false
           if r.child == nil {
               x.next = x
               x.prev = x
               r.child = x
           } else {
               meld1(r.child, x)
           }
           r.rank++
       }
       roots[r.rank] = r
   }
   for r := h.next; r != h.Node; {
       n := r.next
       add(r)
       r = n
   }
   if c := h.child; c != nil {
       c.parent = nil
       r := c.next
       add(c)
       for r != c {
           n := r.next
           r.parent = nil
           add(r)
           r = n
       }
   }
   if len(roots) == 0 {
       h.Node = nil
       return min, true
   }
   var mv *Node
   var d int
   for d, mv = range roots {
       break
   }
   delete(roots, d)
   mv.next = mv
   mv.prev = mv
   for _, r := range roots {
       r.prev = mv
       r.next = mv.next
       mv.next.prev = r
       mv.next = r
       if r.value.LT(mv.value) {
           mv = r
       }
   }
   h.Node = mv
   return min, true

}

// task requirement func (h *Heap) DecreaseKey(n *Node, v Value) error {

   if n.value.LT(v) {
       return fmt.Errorf("DecreaseKey new value greater than existing value")
   }
   n.value = v
   if n == h.Node {
       return nil
   }
   p := n.parent
   if p == nil {
       if v.LT(h.value) {
           h.Node = n
       }
       return nil
   }
   h.cutAndMeld(n)
   return nil

}

func (h Heap) cut(x *Node) {

   p := x.parent
   p.rank--
   if p.rank == 0 {
       p.child = nil
   } else {
       p.child = x.next
       x.prev.next = x.next
       x.next.prev = x.prev
   }
   if p.parent == nil {
       return
   }
   if !p.mark {
       p.mark = true
       return
   }
   h.cutAndMeld(p)

}

func (h Heap) cutAndMeld(x *Node) {

   h.cut(x)
   x.parent = nil
   meld1(h.Node, x)

}

// task requirement func (h *Heap) Delete(n *Node) {

   p := n.parent
   if p == nil {
       if n == h.Node {
           h.ExtractMin()
           return
       }
       n.prev.next = n.next
       n.next.prev = n.prev
   } else {
       h.cut(n)
   }
   c := n.child
   if c == nil {
       return
   }
   for {
       c.parent = nil
       c = c.next
       if c == n.child {
           break
       }
   }
   meld2(h.Node, c)

}

// adapted from task "Visualize a tree" func (h Heap) Vis() {

   if h.Node == nil {
       fmt.Println("<empty>")
       return
   }
   var f func(*Node, string)
   f = func(n *Node, pre string) {
       pc := "│ "
       for x := n; ; x = x.next {
           if x.next != n {
               fmt.Print(pre, "├─")
           } else {
               fmt.Print(pre, "└─")
               pc = "  "
           }
           if x.child == nil {
               fmt.Println("╴", x.value)
           } else {
               fmt.Println("┐", x.value)
               f(x.child, pre+pc)
           }
           if x.next == n {
               break
           }
       }
   }
   f(h.Node, "")

}</lang> A demonstration: <lang go>package main

import (

   "fmt"

   "fib"

)

type str string

func (s str) LT(t fib.Value) bool { return s < t.(str) }

func main() {

   fmt.Println("MakeHeap:")
   h := fib.MakeHeap()
   h.Vis()

   fmt.Println("\nInsert:")
   h.Insert(str("cat"))
   h.Vis()

   fmt.Println("\nUnion:")
   h2 := fib.MakeHeap()
   h2.Insert(str("rat"))
   h.Union(h2)
   h.Vis()

   fmt.Println("\nMinimum:")
   m, _ := h.Minimum()
   fmt.Println(m)

   fmt.Println("\nExtractMin:")
   // add a couple more items to demonstrate parent-child linking that
   // happens on delete min.
   h.Insert(str("bat"))
   x := h.Insert(str("meerkat")) // save x for decrease key and delete demos
   m, _ = h.ExtractMin()
   fmt.Printf("(extracted %v)\n", m)
   h.Vis()

   fmt.Println("\nDecreaseKey:")
   h.DecreaseKey(x, str("gnat"))
   h.Vis()
   fmt.Println("\nDelete:")
   // add yet a couple more items to show how F&T's original delete was
   // lazier than CLRS's delete.
   h.Insert(str("bobcat"))
   h.Insert(str("bat"))
   fmt.Printf("(deleting %v)\n", x.Value())
   h.Delete(x)
   h.Vis()

}</lang>

Output:

MakeHeap:
<empty>

Insert:
└─╴ cat

Union:
├─╴ cat
└─╴ rat

Minimum:
cat

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

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

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

Julia

Translation of: Python

<lang julia>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)

1. 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 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

1. return min node in O(1) time

findmin(h::FibonacciHeap) = h.minnode Minimum(H) = findmin(H) # Minimum(H) for task

1. 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

1. 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

1. 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)
       cascadingcut(root, 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)

1. merge two fibonacci heaps in O(1) time by concatenating the root lists
2. the root of the new root list becomes equal to the first list and the second
3. 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

1. if a child node becomes smaller than its parent node we
2. 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

1. cascading cut of parent node to obtain good time bounds

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

end

1. combine root nodes of equal degree to consolidate the heap
2. 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
           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
   end

end

1. actual linking of one node to another in the root list
2. 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

1. 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

1. 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

1. 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

1. 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

</lang>

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

<lang scala>// version 1.2.21

class Node<V : Comparable<V>>(var value: V) {

   var parent: Node<V>? = null
   var child:  Node<V>? = null
   var prev:   Node<V>? = null
   var next:   Node<V>? = null
   var rank = 0
   var mark = false

   fun meld1(node: Node<V>) {
       this.prev?.next = node
       node.prev = this.prev
       node.next = this
       this.prev = node
   }

   fun meld2(node: Node<V>) {
       this.prev?.next = node
       node.prev?.next = this
       val temp = this.prev
       this.prev = node.prev
       node.prev = temp
   }

}

// task requirement fun <V: Comparable<V>> makeHeap() = FibonacciHeap<V>()

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

   // task requirement
   fun insert(v: V): Node<V> {
       val x = Node(v)
       if (this.node == null) {
           x.next = x
           x.prev = x
           this.node = x
       }
       else {
           this.node!!.meld1(x)
           if (x.value < this.node!!.value) this.node = x
       }
       return x
   }

   // task requirement
   fun union(other: FibonacciHeap<V>) {
       if (this.node == null) {
           this.node = other.node
       }
       else if (other.node != null) {
           this.node!!.meld2(other.node!!)
           if (other.node!!.value < this.node!!.value) this.node = other.node
       }
       other.node = null
   }

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

   // task requirement
   fun extractMin(): V? {
       if (this.node == null) return null
       val min = minimum()
       val roots = mutableMapOf<Int, Node<V>>()

       fun add(r: Node<V>) {
           r.prev = r
           r.next = r
           var rr = r
           while (true) {
               var x = roots[rr.rank] ?: break
               roots.remove(rr.rank)
               if (x.value < rr.value) {
                   val t = rr
                   rr = x
                   x = t
               }
               x.parent = rr
               x.mark = false
               if (rr.child == null) {
                   x.next = x
                   x.prev = x
                   rr.child = x
               }
               else {
                   rr.child!!.meld1(x)
               }
               rr.rank++
           }
           roots[rr.rank] = rr
       }

       var r = this.node!!.next
       while (r != this.node) {
           val n = r!!.next
           add(r)
           r = n
       }
       val c = this.node!!.child
       if (c != null) {
           c.parent = null
           var rr = c.next!!
           add(c)
           while (rr != c) {
               val n = rr.next!!
               rr.parent = null
               add(rr)
               rr = n
           }
       }
       if (roots.isEmpty()) {
           this.node = null
           return min
       }
       val d = roots.keys.first()
       var mv = roots[d]!!
       roots.remove(d)
       mv.next = mv
       mv.prev = mv
       for ((_, rr) in roots) {
           rr.prev = mv
           rr.next = mv.next
           mv.next!!.prev = rr
           mv.next = rr
           if (rr.value < mv.value) mv = rr
       }
       this.node = mv
       return min
   }

   // task requirement
   fun decreaseKey(n: Node<V>, v: V) {
       require (n.value > v) {
           "In 'decreaseKey' new value greater than existing value"
       }
       n.value = v
       if (n == this.node) return
       val p = n.parent
       if (p == null) {
           if (v < this.node!!.value) this.node = n
           return
       }
       cutAndMeld(n)
   }

   private fun cut(x: Node<V>) {
       val p = x.parent
       if (p == null) return
       p.rank--
       if (p.rank == 0) {
           p.child = null
       }
       else {
           p.child = x.next
           x.prev?.next = x.next
           x.next?.prev = x.prev
       }
       if (p.parent == null) return
       if (!p.mark) {
           p.mark = true
           return
       }
       cutAndMeld(p)
   }

   private fun cutAndMeld(x: Node<V>) {
       cut(x)
       x.parent = null
       this.node?.meld1(x)
   }

   // task requirement
   fun delete(n: Node<V>) {
       val p = n.parent
       if (p == null) {
           if (n == this.node) {
               extractMin()
               return
           }
           n.prev?.next = n.next
           n.next?.prev = n.prev
       }
       else {
           cut(n)
       }
       var c = n.child
       if (c == null) return
       while (true) {
           c!!.parent = null
           c = c.next
           if (c == n.child) break
       }
       this.node?.meld2(c!!)
   }

   fun visualize() {
       if (this.node == null) {
           println("<empty>")
           return
       }

       fun f(n: Node<V>, pre: String) {
           var pc = "│ "
           var x = n
           while (true) {
               if (x.next != n) {
                   print("$pre├─")
               }
               else {
                   print("$pre└─")
                   pc = "  "
               }
               if (x.child == null) {
                   println("╴ ${x.value}")
               }
               else {
                   println("┐ ${x.value}")
                   f(x.child!!, pre + pc)
               }
               if (x.next == n) break
               x = x.next!!
           }
       }
       f(this.node!!, "")
   }

}

fun main(args: Array<String>) {

   println("MakeHeap:")
   val h = makeHeap<String>()
   h.visualize()

   println("\nInsert:")
   h.insert("cat")
   h.visualize()

   println("\nUnion:")
   val h2 = makeHeap<String>()
   h2.insert("rat")
   h.union(h2)
   h.visualize()

   println("\nMinimum:")
   var m = h.minimum()
   println(m)

   println("\nExtractMin:")
   // add a couple more items to demonstrate parent-child linking that
   // happens on delete min.
   h.insert("bat")
   val x = h.insert("meerkat")  // save x for decrease key and delete demos.
   m = h.extractMin()
   println("(extracted $m)")
   h.visualize()

   println("\nDecreaseKey:")
   h.decreaseKey(x, "gnat")
   h.visualize()

   println("\nDelete:")
   // add a couple more items.
   h.insert("bobcat")
   h.insert("bat")
   println("(deleting ${x.value})")
   h.delete(x)
   h.visualize()

}</lang>

Output:

MakeHeap:
<empty>

Insert:
└─╴ cat

Union:
├─╴ cat
└─╴ rat

Minimum:
cat

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

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

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

Nim

Translation of: Go & Kotlin

<lang Nim>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

1. Task requirement.

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

1. 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

1. 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

1. 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

1. 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

1. 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)

1. 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)

1. 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()</lang>

Output:

MakeHeap:
<empty>

Insert:
└─╴cat

Union:
├─╴cat
└─╴rat

Minimum:
cat

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

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

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

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
 
-- task requirement
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

-- task requirement
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

-- task requirement
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
 
-- task requirement
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
 
-- task requirement
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]
        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 if
end procedure
 
-- task requirement
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
 
-- task requirement
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

<lang python>class FibonacciHeap:

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

Raku

Translation of: Go & Kotlin

<lang perl6># 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;</lang>

Output:

MakeHeap:
<empty>

Insert:
└─╴cat

Union:
├─╴cat
└─╴rat

Minimum:
cat

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

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

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

Wren

Translation of: Kotlin

Library: Wren-str

This just deals with nodes whose values are strings. <lang ecmascript>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()</lang>

Output:

MakeHeap:
<empty>

Insert:
└─╴ cat

Union:
├─╴ cat
└─╴ rat

Minimum:
cat

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

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

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