StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POCorrect functional implementation on Binomial Heap
text
Body
copied!<p>I am reading <code>Binomial Heap</code> in <a href="http://www.amazon.co.uk/gp/product/0521663504/ref=s9_simh_gw_p14_d2_i1?pf_rd_m=A3P5ROKL5A1OLE&pf_rd_s=center-4&pf_rd_r=14JNZQW0XAQ5PY6VA6VX&pf_rd_t=101&pf_rd_p=430173587&pf_rd_i=468294" rel="nofollow">Purely Functional Data Structures</a>. </p> <p>The implementation of <code>insTree</code> function confused me quite much. Here are the set of codes</p> <pre><code>datatype Tree = Node of int * Elem.T * Tree list fun link (t1 as Node (r, x1, c1), t2 as Node (_, x2, c2)) = if Elem.leq (x1, x2) then Node (r+1, x1, t2::c1) else Node (r+1, x2, t1::c2) fun rank (Node (r, x, c)) = r fun insTree (t, []) = [t] | insTree (t, ts as t' :: ts') = if rank t < rank t' then t::ts else insTree (link (t, t'), ts') </code></pre> <p>My confusion lies on the bit in <code>insTree</code> that <strong>why it does not consider the situation of rank t > rank t'</strong>?</p> <p>In <code>if rank t < rank t' then t::ts else insTree (link (t, t'), ts')</code>, </p> <ol> <li>if t's rank is <strong>less</strong> than t''s rank, then put the t into the heap, no question asked</li> <li>the <em>else</em> has two cases: <strong>equal</strong> and <strong>bigger</strong>. </li> <li>For <strong>equal</strong>, yes, we can link two trees (we link only two trees with the same rank), and then try to insert the new linked tree into the heap, no question asked.</li> <li>but even the <strong>bigger</strong> case would have the same as equal, <strong>why?</strong> Even if rank t > rank t', we still link them?</li> </ol> <hr> <h2>Edit</h2> <p>I thought the process of <code>inserting a binomial tree into a binomial heap</code> should be like this:</p> <ol> <li>We get the tree t and the heap</li> <li>In the heap (actually a list), we compare rank of the tree t with every tree in the heap</li> <li>We find a missing rank (increasing order in the heap) which matches the rank of t, we put t at that slot</li> <li>We find a tree in the heap with same rank as t, then we link two trees and process a <code>rank+1</code> new tree and try again insert the new tree to the heap.</li> </ol> <p>So, I think the correct <code>fun insTree</code> could be like this:</p> <pre><code>fun insTree (t, []) = [t] | insTree (t, ts as t' :: ts') = if rank t < rank t' then t::ts else if rank t = rank t' then insTree (link (t, t'), ts') else t'::(insTree (t, ts')) </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload