ya "orderd statistics" refer cormen book .It uses a slightly modified
version of quick sort.

On Jan 14, 8:01 pm, saurabh singh <saurab...@gmail.com> wrote:
> nth order statistics <http://en.wikipedia.org/wiki/Selection_algorithm>
> Saurabh Singh
> B.Tech (Computer Science)
> MNNIT
> blog:geekinessthecoolway.blogspot.com
>
> On Sat, Jan 14, 2012 at 8:23 PM, Piyush Grover 
> <piyush4u.iit...@gmail.com>wrote:
>
>
>
>
>
>
>
> > you can do it in nlogk or n+klogn time.
>
> > create a min-heap tree of size k with first k nodes.
> > Add k+1..n nodes in the tree. Everytime you insert a node in the tree
> > check if it's greater than the root node. If yes remove
> > root node and insert the new node (logk operations). So time complexity
> > will be nlogk.
>
> > another method with time complexity n+ klogn
> > create a max heap tree of size n. O(n)
>
> > keep on deleting the root node for k-1 operations by maintaining the heap
> > property. Finally you will be left with the kth largest mode at the root.
> > O(klogn)
>
> > On Sat, Jan 14, 2012 at 7:58 PM, Ashish Goel <ashg...@gmail.com> wrote:
>
> >> Hi,
>
> >> how can we do so in O(n)
> >> forming a heap or a tree with each node keeping children in its left node
> >> still is nlogn
>
> >> Best Regards
> >> Ashish Goel
> >> "Think positive and find fuel in failure"
> >> +919985813081
> >> +919966006652
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@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.
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.

Reply via email to