Fibonacci heap: Difference between revisions
m
→{{header|Julia}}
Line 588:
export FNode, FibonacciHeap, insert, extractmin, findmin, decreasekey, delete!
export Insert, MakeHeap, Minimum, ExtractMin, DecreaseKey, Delete
import Base.print
mutable struct FNode{T}
Line 624:
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
Line 817 ⟶ 848:
function delete!(root, node)
if (parent = node.parent) == nothing
if node.child
end
remove_from_root_list(root, node)
else
remove_from_child_list(root, parent, node)
Line 828 ⟶ 860:
end # module
using .FibonacciHeaps
</lang>▼
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)
▲</lang>{{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
</pre>
=={{header|Kotlin}}==
| |||