Re: [algogeeks] Re: What is the time to get min element from the binary max heap !!
If we know the size of heap we can get the minimum element in O(n); int findMinFromMaxHeap(int ar[], int n) { if ( (n+1) & n == 0) { for (i = n>>1; i < n; i++) min = min > ar[i] ? ar[i] : min; } else { int x = n, y = 1; while(x >1) { y <<= 1; x >>= 1; } y -= 1; x = (n - y + 1) / 2; for (i = y / 2 + x; i < n; i++) min = min > ar[i] ? ar[i] : min; } return min; } -- 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.
Re: [algogeeks] Re: What is the time to get min element from the binary max heap !!
its O(nlogn) only... n v cant directly access d leaf element... since d leaf elements are n(n-1)/2so last dese many elemnts will found n compared... Regards, PAYAL GUPTA, CSE-3rd yr NIT_B On Tue, Sep 20, 2011 at 10:54 PM, saurabh agrawal wrote: > How will you directly access the leaf nodes, you dont have the heap > implementation, you are just provided with the API. :) > > > > On Tue, Sep 20, 2011 at 9:55 PM, sukran dhawan wrote: > >> o(n) >> >> >> On Tue, Sep 20, 2011 at 6:42 PM, CHERUVU JAANU REDDY < >> jaanu.cher...@gmail.com> wrote: >> >>> >>> We can find minimum element in O(n) time. >>> >>> Just compare leaf nodes in max heap tree. >>> >>> >>> >>> Cheers >>> Janardhan Reddy Cheruvu >>> +91-9642421117 >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> >>> On Tue, Sep 20, 2011 at 6:39 PM, saurabh agrawal >>> wrote: >>> I think, we have to delete all the elements from the heap which takes o(n*logn). Please share if you have any better solutions. On Tue, Sep 20, 2011 at 6:38 PM, saurabh agrawal wrote: > What is the time to get min element from the binary max heap !! > You might be given the heap as API. I mean, you dont have > implementation of the heap. > -- 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. >> > > -- > 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.
Re: [algogeeks] Re: What is the time to get min element from the binary max heap !!
How will you directly access the leaf nodes, you dont have the heap implementation, you are just provided with the API. :) On Tue, Sep 20, 2011 at 9:55 PM, sukran dhawan wrote: > o(n) > > > On Tue, Sep 20, 2011 at 6:42 PM, CHERUVU JAANU REDDY < > jaanu.cher...@gmail.com> wrote: > >> >> We can find minimum element in O(n) time. >> >> Just compare leaf nodes in max heap tree. >> >> >> >> Cheers >> Janardhan Reddy Cheruvu >> +91-9642421117 >> >> >> >> >> >> >> >> >> >> >> >> On Tue, Sep 20, 2011 at 6:39 PM, saurabh agrawal wrote: >> >>> I think, we have to delete all the elements from the heap which takes >>> o(n*logn). Please share if you have any better solutions. >>> >>> On Tue, Sep 20, 2011 at 6:38 PM, saurabh agrawal >>> wrote: >>> What is the time to get min element from the binary max heap !! You might be given the heap as API. I mean, you dont have implementation of the heap. >>> >>> -- >>> 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. > -- 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.
Re: [algogeeks] Re: What is the time to get min element from the binary max heap !!
o(n) On Tue, Sep 20, 2011 at 6:42 PM, CHERUVU JAANU REDDY < jaanu.cher...@gmail.com> wrote: > > We can find minimum element in O(n) time. > > Just compare leaf nodes in max heap tree. > > > > Cheers > Janardhan Reddy Cheruvu > +91-9642421117 > > > > > > > > > > > > On Tue, Sep 20, 2011 at 6:39 PM, saurabh agrawal wrote: > >> I think, we have to delete all the elements from the heap which takes >> o(n*logn). Please share if you have any better solutions. >> >> On Tue, Sep 20, 2011 at 6:38 PM, saurabh agrawal wrote: >> >>> What is the time to get min element from the binary max heap !! >>> You might be given the heap as API. I mean, you dont have implementation >>> of the heap. >>> >> >> -- >> 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.
Re: [algogeeks] Re: What is the time to get min element from the binary max heap !!
We can find minimum element in O(n) time. Just compare leaf nodes in max heap tree. Cheers Janardhan Reddy Cheruvu +91-9642421117 On Tue, Sep 20, 2011 at 6:39 PM, saurabh agrawal wrote: > I think, we have to delete all the elements from the heap which takes > o(n*logn). Please share if you have any better solutions. > > On Tue, Sep 20, 2011 at 6:38 PM, saurabh agrawal wrote: > >> What is the time to get min element from the binary max heap !! >> You might be given the heap as API. I mean, you dont have implementation >> of the heap. >> > > -- > 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.
[algogeeks] Re: What is the time to get min element from the binary max heap !!
I think, we have to delete all the elements from the heap which takes o(n*logn). Please share if you have any better solutions. On Tue, Sep 20, 2011 at 6:38 PM, saurabh agrawal wrote: > What is the time to get min element from the binary max heap !! > You might be given the heap as API. I mean, you dont have implementation of > the heap. > -- 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.