Dear All,
I found this in the book by skeina.
Problem: Given an array-based heap on n elements and a real number x,
efficiently
determine whether the kth smallest element in the heap is greater than or
equal
to x. Your algorithm should be O(k) in the worst-case, independent of the
size of
the heap.
the solution is given as follows.
int heap_compare(priority_queue *q, int i, int count, int x)
{
if ((count <= 0) || (i > q->n) return(count);
if (q->q[i] < x) {
count = heap_compare(q, pq_young_child(i), count-1, x);
count = heap_compare(q, pq_young_child(i)+1, count, x);
}
return(count);
}
The explanation is given as follows:
This procedure searches
the children of all nodes of weight smaller than x until either (a) we have
found
k of them, when it returns 0, or (b) they are exhausted, when it returns a
value
greater than zero. Thus it will find enough small elements if they exist.
But how long does it take? The only nodes whose children we look at are
those
< x, and at most k of these in total. Each have at most visited two
children, so we
visit at most 3k nodes, for a total time of O(k).
I dont see how it works. In particular I dont see why count is reset
according to the 2 children of the current node. I am new to this. can some1
explain me what's happening?
Many thank,
Ashim
--
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.
