oops... wanted to write the same but yeah its meaning turns out to be totally different :( anyways very well explained by Lucifier
@shashank i think now u will be able to get why there will be only 2k comparisons in the worst case On Thu, Dec 15, 2011 at 10:51 PM, atul anand <[email protected]>wrote: > @Lucifer : yes even i found flaw in the above algo when i gave it a second > thought but didnt get time to post it. > bcoz min heap has property that the parent node is less than its both > child(subtree to be more precise ) but it does not confirm that left child > is always smaller than right child of the node. > > > On Thu, Dec 15, 2011 at 10:31 PM, Lucifer <[email protected]> wrote: > >> @All >> >> I don't think the algo given above is entirely correct.. Or may be i >> didn't it properly... >> >> So basically say a preorder traversal of the heap is done based on >> whether the current root value < X. As the algo says that at any point >> if k>0 and we hit a node value which is >=X , then we are done. If i >> understood it properly then thats not correct. >> >> The reason being that say on the left subtree we end up at a node >> whose value is >=x and say k > 0. Now until and unless we don't parse >> the right subtree (or basically the right half which was neglected as >> part of pre-order traversal or say was to be considered later) we are >> not sure if the current node is actually withing the first smallest K >> nos. It may happen that previously neglected (or rather later to be >> processed) half has the kth smallest element which is actually < X. >> The reason being that a heap is not a binary search tree where there >> is a strict relation between the left and the right half so that we >> can say that if say a condition P is true in the left half then it >> will be false in the right half and vice versa. >> >> To solve the problem we need to do a pre-order traversal keeping the >> following conditions in mind: (pass K and root node) >> >> 1) If current node is >= X then skip the processing of the tree rooted >> at the current node. >> >> 2) If current node is < X , then decrement K by 1 and process its >> childs ( i.e take step 1 for rach child). >> >> The result will depend on: >> >> a) If at any stage recursion ends and the value of K>0 then the kth >> smallest element is >= X. >> b) If during tree traversal the value of K reaches 0, that means >> there are atleast k elements which are < X. Hence, at this point >> terminate the recursion ( as in no need to continue). This result >> signifies that the kth smallest element < X. >> >> Therefore to generalize... >> >> Perform a preorder traversal for root node < X, and keep decrementing >> the count K by 1. >> If K reaches 0 during traversal then end the recursion. >> >> After the call to the recursive traversal is over, check for the value >> of K. If greater than 0, then the kth smallest element >= X otherwise >> its not. >> >> The time complexity will always be 2K ( in the worst case basically >> when K value reaches 0 ). If u analyze it closely we are making 2 >> checks when at particular node for its children. Hence, whether both >> the child nodes have value < X or one of them or node, at the end we >> always end up making 2 checks for the children (left and right child). >> So given any tree one can think of a null node as a leaf node >> ( depicting that the node has a value >=X) . Hence, for any given bin- >> tree having nodes 'N', the number null nodes is 'N+1'. Hence, the >> total number of checks will be 2N+1 = O(2N) , >> >> >> On Dec 15, 1:00 pm, WgpShashank <[email protected]> wrote: >> > @sunny why we look at all k number which are greater then x , correct ? >> > Lets think in this way >> > >> > we wants to check if kth smallest element in heap thats >=x isn't it ? >> so >> > if root of mean heap is greater then x then none other elements will >> less >> > then x so we terminate . >> > else our algorithm will search children of all the nodes which are less >> > then x till either we have found k of them or we are exhausted e.g. >> when >> > k=0 . so we will cal our function to both left & right children ? >> > >> > so now think we are looking for children's of only nodes which are less >> > then x and at most k of these in tottal . each have atmost two visited >> > childrens so we have visted at-most 3K nodes isn;t it ? for total time >> O(K) >> > ? >> > >> > let me know where i am wrong ? i am not getting for uy k nodes greater >> then >> > x ? why we will do that & then how much comparisons u needs for that ? >> > >> > Thanks >> > Shashank Mani >> > CSE, BIT Mesrahttp://shashank7s.blogspot.com/ >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Sunny Aggrawal B.Tech. V year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
