Mercurial > lbo > hg > juliaplay
view heap.jl @ 0:d0c890aae379
Initial commit
author | Lewin Bormann <lbo@spheniscida.de> |
---|---|
date | Sat, 26 Nov 2022 09:23:14 +0100 |
parents | |
children |
line wrap: on
line source
function heap_parent(ix::Int)::Int max(1, round(Int, floor(ix/2))) end function heap_children(ix::Int)::Tuple{Int,Int} (2ix, 2ix+1) end function heap_bubble!(h::Vector{Int}, ix::Int) if ix == 1 return end hp = heap_parent(ix) if h[hp] > h[ix] h[hp], h[ix] = h[ix], h[hp] end heap_bubble!(h, hp) end # Min-heap function heap_insert!(h::Vector{Int}, n::Int) push!(h, n) ix = length(h) heap_bubble!(h, ix) end function heap_pull!(h::Vector{Int}, ix::Int) l, r = heap_children(ix) if l <= length(h) && r <= length(h) if h[l] < h[r] h[ix], h[l] = h[l], h[ix] heap_pull!(h, l) else h[ix], h[r] = h[r], h[ix] heap_pull!(h, r) end elseif l <= length(h) @assert l == length(h) h[ix], h[l] = h[l], h[ix] popat!(h, length(h)) else h[ix] = 10000 end end function heap_pop!(h::Vector{Int})::Int e = h[1] heap_pull!(h, 1) e end