Just do a little changes on your given function, that may help you
understand it:
We denote the transformed function as heap_compare_new:
int heap_compare_new(priority_queue *q, int i, int count, int x)
{
if ((count >= k) || (i > q->n) return(k-count);
/* change */
if (q->q[i] < x) {
count++;
/* add one line */
count = heap_compare_new(q, pq_young_child(i), count, x);
/* change */
count = heap_compare_new(q, pq_young_child(i)+1, count, x);
}
return(count);
}
Is that clear now? The new function is used to count the number of
nodes, whose keys are smaller than x, in a subtree rooted on node i,
with a count base, represented by the parameter count, which means
that I have already known that there exist count nodes outside this
subtree having keys smaller than x. And once count becomes equal to k,
the procedure will end and return.
Actually heap_compare_new does the same thing as heap_compare. Here I
just made a minor adjustment that I turned variable 'count' in
original function to the 'k - count' version. The count parameters in
these two functions serve as the same role which I call "the count
base".
On Aug 21, 6:11 pm, Ashim Kapoor <ashimkap...@gmail.com> wrote:
> sure, but the implementation is confusing. My question is does not the 2nd
> count overwrite the 1st value of count in side the function?
>
> Thank you.
>
> On Sun, Aug 22, 2010 at 1:04 AM, Harshal ..Bet oN iT!!
> <hc4...@gmail.com>wrote:
>
>
>
> > if it is a min heap,, then traversing down from the root node, it takes
> > O(k) time to reach the kth smallest element. so, i think its just that
> > straight!!! plz correct me if m wrong???
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
