Fibonacci heap: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (18 intermediate revisions by 10 users not shown) | |||
Line 1:
;Task:
* Implement queue operations for
*Operations:
** MakeHeap() - create new empty Fibonacci heap
Line 9 ⟶ 11:
** 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) -
** Delete(H,x) - remove element x from heap H
<br><br>
=={{header|C++}}==
<syntaxhighlight lang="cpp">template <class V> class FibonacciHeap;
template <class V> struct node {
Line 272 ⟶ 86:
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() {
Line 351 ⟶ 177:
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;
Line 367 ⟶ 189:
t->next=n->next;
t->prev=n->prev;
}
_addChild(t,n);
n=t;
}
continue;
Line 395 ⟶ 217:
n->next=n->prev=n;
n->marked=false;
n->parent->degree--;
return _merge(heap,n);
}
Line 401 ⟶ 224:
if(n->value<value)return heap;
n->value=value;
if(parent != nullptr && n->value < parent->value) {
heap=_cut(heap,n);
n->parent=NULL;
while(parent!=NULL && parent->marked) {
Line 412 ⟶ 235:
}
if(parent!=NULL && parent->parent!=NULL)parent->marked=true;
if (n->value < heap->value)heap = n;
}
return heap;
Line 427 ⟶ 251:
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;
}
</syntaxhighlight>
=={{header|Go}}==
A package. Implementation follows Fredman and Tarjan's 1987 paper.
<syntaxhighlight 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, "")
}</syntaxhighlight>
A demonstration:
<syntaxhighlight 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()
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight 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
</syntaxhighlight>{{out}}
<pre>
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
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight 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()
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Nim}}==
{{trans|Go & Kotlin}}
<syntaxhighlight 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()</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Phix}}==
{{trans|Go}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">VALUE</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">PARENT</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">CHILD</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">PREV</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NEXT</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">RANK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">MARK</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">NODELEN</span><span style="color: #0000FF;">=$</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">new_node</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">NODELEN</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">freelist</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">new_slot</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">freelist</span><span style="color: #0000FF;">!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freelist</span>
<span style="color: #000000;">freelist</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">freelist</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">res</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">nodes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">release_slot</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freelist</span>
<span style="color: #000000;">freelist</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">MakeHeap</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">new_slot</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">meld1</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">list</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">single</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">list</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">single</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">single</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">list</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">single</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">list</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">list</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">single</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (helps with refcounts for pwa/p2js)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">new_node</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span>
<span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">new_slot</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">meld1</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">meld2</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">a</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">b</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">a</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">a</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">b</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">a</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Union</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h2</span>
<span style="color: #008080;">elsif</span> <span style="color: #008080;">not</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">meld2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">release_slot</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (h2:=NULL implied)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Minimum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"<none>"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">],</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">add_roots</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">node</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">],</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">node</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">node</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">],</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">MARK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">meld1</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">],</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">ExtractMin</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"<none>"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">minimum</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">roots</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">h</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">add_roots</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">!=</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">add_roots</span><span style="color: #0000FF;">(</span><span style="color: #000000;">c</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">!=</span> <span style="color: #000000;">c</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #000000;">add_roots</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">minimum</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mv</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mv</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mv</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_all_keys</span><span style="color: #0000FF;">(</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">rs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mv</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">r</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mv</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mv</span>
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">minimum</span><span style="color: #0000FF;">,</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">cut_and_meld</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">meld</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">RANK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">MARK</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">][</span><span style="color: #000000;">MARK</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">cut_and_meld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">meld</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #000000;">meld1</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">DecreaseKey</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">object</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]<</span><span style="color: #000000;">v</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"DecreaseKey new value greater than existing value"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">v</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">h</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">v</span><span style="color: #0000FF;"><</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">h</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">cut_and_meld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">h</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000080;font-style:italic;">-- task requirement</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">Delete</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">h</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ExtractMin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">h</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PREV</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">cut_and_meld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">!=</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">PARENT</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">c</span><span style="color: #0000FF;">][</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">meld2</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">h</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">W</span><span style="color: #0000FF;">=</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">WINDOWS</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">Horizontal</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">?</span><span style="color: #000000;">#C4</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">Vertical</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">?</span><span style="color: #000000;">#B3</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'|'</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sBtmLeft</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">?</span><span style="color: #000000;">#C0</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sLeftTee</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">?</span><span style="color: #000000;">#C3</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">sTopRight</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">W</span><span style="color: #0000FF;">?</span><span style="color: #000000;">#BF</span><span style="color: #0000FF;">:</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">vis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">pre</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">pc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Vertical</span><span style="color: #0000FF;">&</span><span style="color: #008000;">" "</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">NEXT</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pre</span><span style="color: #0000FF;">&</span><span style="color: #000000;">sLeftTee</span><span style="color: #0000FF;">&</span><span style="color: #000000;">Horizontal</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pre</span><span style="color: #0000FF;">&</span><span style="color: #000000;">sBtmLeft</span><span style="color: #0000FF;">&</span><span style="color: #000000;">Horizontal</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">pc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">==</span> <span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%c %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">Horizontal</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%c %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">sTopRight</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">])})</span>
<span style="color: #000000;">vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">[</span><span style="color: #000000;">CHILD</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">pre</span><span style="color: #0000FF;">&</span><span style="color: #000000;">pc</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">next</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">is_null</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"<empty>\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"MakeHeap:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">MakeHeap</span><span style="color: #0000FF;">()</span>
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nInsert:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"cat"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nUnion:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">h2</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">MakeHeap</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"rat"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Union</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (h2:=NULL)</span>
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Minimum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nMinimum:\n%v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">m</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nExtractMin:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- add a couple more items to demonstrate parent-child linking that
-- happens on delete min.</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bat"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"meerkat"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- save x for decrease key and delete demos</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ExtractMin</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(extracted %s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nDecreaseKey:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">DecreaseKey</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"gnat"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\nDelete:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- add yet a couple more items to show how F&T's original delete was
-- lazier than CLRS's delete.</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bobcat"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Insert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"bat"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"(deleting %s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">nodes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">][</span><span style="color: #000000;">VALUE</span><span style="color: #0000FF;">])})</span>
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">Delete</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
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"
</pre>
=={{header|Python}}==
<syntaxhighlight 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</syntaxhighlight>
=={{header|Raku}}==
{{trans|Go & Kotlin}}
<syntaxhighlight lang="raku" line># 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;</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-str}}
This just deals with nodes whose values are strings.
<syntaxhighlight lang="wren">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()</syntaxhighlight>
{{out}}
<pre>
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
</pre>
| |||