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