Fibonacci heap: Difference between revisions
Content added Content deleted
Line 581: | Line 581: | ||
└─╴ rat |
└─╴ rat |
||
</pre> |
</pre> |
||
=={{header|Julia}}== |
|||
{{trans|Python}} |
|||
<lang julia>module FibonacciHeaps |
|||
export FNode, FibonacciHeap, insert, extractmin, findmin, decreasekey, delete! |
|||
export Insert, MakeHeap, Minimum, ExtractMin, DecreaseKey, Delete |
|||
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 |
|||
# 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 in aslist(root.rootlist) |
|||
remove_from_root_list(root, node) |
|||
end |
|||
else |
|||
remove_from_child_list(root, parent, node) |
|||
end |
|||
end |
|||
Delete(H, x) = delete!(H, x) # Delete(H, x) for task |
|||
end # module |
|||
</lang> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |