Rosetta Code

Fibonacci heap: Difference between revisions

Page Discussion

Fibonacci heap (view source)

Revision as of 17:15, 16 January 2022

65,585 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring, made p2js compatible
m (→‎{{header|Phix}}: added syntax colouring, made p2js compatible)
Line 1,623:
=={{header|Phix}}==
{{trans|Go}}
<!--<lang Phix>(phixonline)-->
<lang Phix>enum VALUE, PARENT, CHILD, PREV, NEXT, RANK, MARK, NODELEN=$
<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>
function new_node()
return repeat(NULL,NODELEN)
<span style="color: #008080;">function</span> <span style="color: #000000;">new_node</span><span style="color: #0000FF;">()</span>
end function
<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>
sequence nodes = {}
integer freelist = NULL
<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>
function new_slot()
integer res
<span style="color: #008080;">function</span> <span style="color: #000000;">new_slot</span><span style="color: #0000FF;">()</span>
if freelist!=NULL then
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span>
res = freelist
<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>
freelist = nodes[freelist]
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">freelist</span>
nodes[freelist] = NULL
<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>
else
<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>
nodes = append(nodes,NULL)
<span style="color: #008080;">else</span>
res = length(nodes)
<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>
end if
<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>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure release_slot(integer n)
nodes[n] = freelist
<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>
freelist = n
<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>
end procedure
<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>
-- task requirement
function MakeHeap()
<span style="color: #000080;font-style:italic;">-- task requirement</span>
return new_slot()
<span style="color: #008080;">function</span> <span style="color: #000000;">MakeHeap</span><span style="color: #0000FF;">()</span>
end function
<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>
procedure meld1(integer list, single)
<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>
nodes[nodes[list][PREV]][NEXT] = single
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
nodes[single][PREV] = nodes[list][PREV]
<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>
nodes[single][NEXT] = list
<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>
nodes[list][PREV] = single
<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>
end procedure
<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>
-- task requirement
<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>
function Insert(integer h, object v)
<span style="color: #008080;">else</span>
integer n = 0
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">new_slot</span><span style="color: #0000FF;">()</span>
sequence x = new_node()
<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>
x[VALUE] = v
<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>
if nodes[h] == NULL then
<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>
x[NEXT] = h
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
x[PREV] = h
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
nodes[h] = x
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
else
<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>
n = new_slot()
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
nodes[n] = x
meld1(h, n)
<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>
if nodes[n][VALUE]<nodes[h][VALUE] then
<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>
h = n
<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>
end if
<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>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
return {h,n}
end function
<span style="color: #000080;font-style:italic;">-- task requirement</span>
procedure meld2(integer a, b)
<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>
nodes[nodes[a][PREV]][NEXT] = b
<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>
nodes[nodes[b][PREV]][NEXT] = a
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h2</span>
{nodes[a][PREV], nodes[b][PREV]} = {nodes[b][PREV], nodes[a][PREV]}
<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>
end procedure
<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>
-- task requirement
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">h2</span>
function Union(integer h, h2)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if nodes[h] == NULL then
<span style="color: #008080;">else</span>
h = h2
<span style="color: #000000;">release_slot</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h2</span><span style="color: #0000FF;">)</span>
elsif nodes[h2] != NULL then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
meld2(h, h2)
<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>
if nodes[h2][VALUE]<nodes[h][VALUE] then
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
h = h2
end if
<span style="color: #000080;font-style:italic;">-- task requirement</span>
else
<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>
release_slot(h2)
<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>
end if
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"&lt;none&gt;"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}</span>
return {h,NULL} -- (h2:=NULL implied)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end function
<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>
-- task requirement
function Minimum(integer h)
<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>
if nodes[h] == NULL then
<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>
return {"<none>",false}
<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>
end if
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
return {nodes[h][VALUE], true}
<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>
end function
<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>
procedure add_roots(integer r, integer roots)
<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>
nodes[r][PREV] = r
<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>
nodes[r][NEXT] = r
<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>
while true do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer node = getd_index(nodes[r][RANK],roots)
<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>
if node=NULL then exit end if
<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>
integer x = getd_by_index(node,roots)
<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>
deld(nodes[r][RANK],roots)
<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>
if nodes[x][VALUE]<nodes[r][VALUE] then
<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>
{r, x} = {x, r}
<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>
end if
<span style="color: #008080;">else</span>
nodes[x][PARENT] = r
<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>
nodes[x][MARK] = false
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if nodes[r][CHILD] == NULL then
<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>
nodes[x][NEXT] = x
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
nodes[x][PREV] = x
<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>
nodes[r][CHILD] = x
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
else
meld1(nodes[r][CHILD], x)
<span style="color: #000080;font-style:italic;">-- task requirement</span>
end if
<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>
nodes[r][RANK] += 1
<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>
end while
<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;">"&lt;none&gt;"</span><span style="color: #0000FF;">,</span><span style="color: #004600;">false</span><span style="color: #0000FF;">}</span>
setd(nodes[r][RANK],r,roots)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<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>
-- task requirement
<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>
function ExtractMin(integer h)
<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>
if nodes[h] == NULL then
<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>
return {h,"<none>",false}
<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>
end if
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
object minimum = nodes[h][VALUE]
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
integer roots = new_dict()
<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>
integer r = nodes[h][NEXT], n
<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>
while r != h do
<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>
n := nodes[r][NEXT]
<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>
add_roots(r,roots)
<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>
r = n
<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>
end while
<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>
integer c = nodes[h][CHILD]
<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>
if c != NULL then
<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>
nodes[c][PARENT] = NULL
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
r := nodes[c][NEXT]
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
add_roots(c,roots)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while r != c do
<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>
n := nodes[r][NEXT]
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
nodes[r][PARENT] = NULL
<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>
add_roots(r,roots)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
r = n
<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>
end while
<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>
end if
<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>
if dict_size(roots) == 0 then
<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>
destroy_dict(roots)
<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>
return {NULL, minimum, true}
<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>
end if
<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>
integer d = getd_partial_key(0,roots)
<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>
integer mv = getd(d,roots)
<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>
deld(d,roots)
<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>
nodes[mv][NEXT] = mv
<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>
nodes[mv][PREV] = mv
<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>
sequence rs = getd_all_keys(roots)
<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>
for i=1 to length(rs) do
<span style="color: #000000;">mv</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">r</span>
r = getd(rs[i],roots)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
nodes[r][PREV] = mv
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
nodes[r][NEXT] = nodes[mv][NEXT]
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mv</span>
nodes[nodes[mv][NEXT]][PREV] = r
<span style="color: #7060A8;">destroy_dict</span><span style="color: #0000FF;">(</span><span style="color: #000000;">roots</span><span style="color: #0000FF;">)</span>
nodes[mv][NEXT] = r
<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>
if nodes[r][VALUE]<nodes[mv][VALUE] then
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
mv = r
end if
<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>
end for
<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>
h = mv
<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>
destroy_dict(roots)
<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>
return {h, minimum, true}
<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>
end function
<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>
procedure cut_and_meld(integer h, x, bool meld)
<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>
integer p := nodes[x][PARENT]
<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>
nodes[p][RANK] -= 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if nodes[p][RANK] == 0 then
<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>
nodes[p][CHILD] = NULL
<span style="color: #008080;">return</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
nodes[p][CHILD] = nodes[x][NEXT]
<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>
nodes[nodes[x][PREV]][NEXT] = nodes[x][NEXT]
<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>
nodes[nodes[x][NEXT]][PREV] = nodes[x][PREV]
<span style="color: #008080;">return</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if nodes[p][PARENT] == NULL then
<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>
return
<span style="color: #008080;">if</span> <span style="color: #000000;">meld</span> <span style="color: #008080;">then</span>
end if
<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>
if not nodes[p][MARK] then
<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>
nodes[p][MARK] = true
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
end if
cut_and_meld(h,p,true)
<span style="color: #000080;font-style:italic;">-- task requirement</span>
if meld then
<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>
nodes[x][PARENT] = NULL
<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>
meld1(h, x)
<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>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<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>
-- task requirement
<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>
function DecreaseKey(integer h, n, object v)
<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>
if nodes[n][VALUE]<v then
<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>
crash("DecreaseKey new value greater than existing value")
<span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
nodes[n][VALUE] = v
<span style="color: #008080;">else</span>
if n!=h then
<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>
integer p := nodes[n][PARENT]
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if p == NULL then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if v<nodes[h][VALUE] then
<span style="color: #008080;">return</span> <span style="color: #000000;">h</span>
h = n
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end if
else
<span style="color: #000080;font-style:italic;">-- task requirement</span>
cut_and_meld(h,n,true)
<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>
end if
<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>
end if
<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>
return h
<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>
end function
<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>
-- task requirement
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
function Delete(integer h, n)
<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>
integer p := nodes[n][PARENT]
<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>
if p == NULL then
<span style="color: #008080;">else</span>
if n == h then
<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>
{h} = ExtractMin(h)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return h
<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>
end if
<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>
nodes[nodes[n][PREV]][NEXT] = nodes[n][NEXT]
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
nodes[nodes[n][NEXT]][PREV] = nodes[n][PREV]
<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>
else
<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>
cut_and_meld(h,n,false)
<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>
end if
<span style="color: #008080;">exit</span>
integer c := nodes[n][CHILD]
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if c != NULL then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
while true do
<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>
nodes[c][PARENT] = NULL
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
c = nodes[c][NEXT]
<span style="color: #008080;">return</span> <span style="color: #000000;">h</span>
if c == nodes[n][CHILD] then
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
exit
end if
<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>
end while
<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>
meld2(h, c)
<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>
end if
<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>
return h
<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>
end function
<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>
constant W=platform()=WINDOWS,
<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>
Horizontal = iff(W?#C4:'-'),
<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>
Vertical = iff(W?#B3:'|'),
<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>
sBtmLeft = iff(W?#C0:'+'),
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
sLeftTee = iff(W?#C3:'+'),
<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>
sTopRight = iff(W?#BF:'+')
<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>
procedure vis(integer n, string pre)
<span style="color: #008080;">else</span>
string pc = Vertical&" "
<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>
sequence x = nodes[n]
<span style="color: #000000;">pc</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" "</span>
while true do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
integer next = x[NEXT]
<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>
if next!=n then
<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>
printf(1,pre&sLeftTee&Horizontal)
<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>
printf(1,pre&sBtmLeft&Horizontal)
<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>
pc = " "
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<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>
if x[CHILD] == NULL then
<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>
printf(1,"%c %s\n",{Horizontal,sprint(x[VALUE])})
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
else
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
printf(1,"%c %s\n",{sTopRight,sprint(x[VALUE])})
vis(x[CHILD], pre&pc)
<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>
end if
<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>
if next=n then exit end if
<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;">"&lt;empty&gt;\n"</span><span style="color: #0000FF;">)</span>
x = nodes[next]
<span style="color: #008080;">return</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end procedure
<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>
procedure Vis(integer h)
if nodes[h] == NULL then
<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>
printf(1,"<empty>\n")
<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>
return
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
end if
vis(h,"")
<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>
end procedure
<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>
printf(1,"MakeHeap:\n")
integer h := MakeHeap()
<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>
Vis(h)
<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>
printf(1,"\nInsert:\n")
<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>
{h} = Insert(h,"cat")
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
Vis(h)
<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>
printf(1,"\nUnion:\n")
<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>
integer h2 := MakeHeap()
{h2} = Insert(h2,"rat")
<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>
{h,h2} = Union(h,h2) -- (h2:=NULL)
<span style="color: #000080;font-style:italic;">-- add a couple more items to demonstrate parent-child linking that
Vis(h)
-- 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>
printf(1,"\nMinimum:\n")
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span>
{object m, {}} = Minimum(h)
<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>
?m
<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>
printf(1,"\nExtractMin:\n")
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
-- add a couple more items to demonstrate parent-child linking that
-- happens on delete min.
<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>
{h} = Insert(h,"bat")
<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>
{h,integer x} = Insert(h,"meerkat") -- save x for decrease key and delete demos
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
{h,m,{}} = ExtractMin(h)
printf(1,"(extracted %s)\n", {sprint(m)})
<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>
Vis(h)
<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>
printf(1,"\nDecreaseKey:\n")
<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>
h = DecreaseKey(h, x, "gnat")
<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>
Vis(h)
<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>
printf(1,"\nDelete:\n")
<span style="color: #000000;">Vis</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
-- add yet a couple more items to show how F&T's original delete was
<!--</lang>-->
-- lazier than CLRS's delete.
{h} = Insert(h,"bobcat")
{h} = Insert(h,"bat")
printf(1,"(deleting %s)\n", {sprint(nodes[x][VALUE])})
h = Delete(h,x)
Vis(h)</lang>
{{out}}
<pre>
Petelomax
7,813

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/276367"