okay but how do you find the nth smallest element in O(1) or O(n) .. if Max/Min Heap are given
On Thu, Mar 27, 2014 at 6:12 PM, Luke Pebody <[email protected]> wrote: > A min heap is a structure that, at it's most basic, has 2 operations: > addToHeap(element) and popAndReturnMin(). > > To use it to sort: > 1) Loop through your array, adding all elements to the heap > 2) N times (where N is the number of elements in the original array) pop > the minimum element of the things left in the heap. > > Done. > > Sent from my iPad > > On 27 Mar 2014, at 16:22, vivek dhiman <[email protected]> wrote: > > how do you extract a sorted array from a Max and a Min heap. > > For example If someone is looping through a very very long array and at > every step you want to get a sorted array of elements, it is better not to > sort every time. Although it is easier to maintain a Min-Heap and Max-Heap. > But how do you obtain a sorted array from a Min Heap and Mx-Heap? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/CABaJBvKvZ8M_EB8_imLoEvdEsa4uUT%3DnQuvzN5ZGft_t3rYzsw%40mail.gmail.com<https://groups.google.com/d/msgid/google-code/CABaJBvKvZ8M_EB8_imLoEvdEsa4uUT%3DnQuvzN5ZGft_t3rYzsw%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/4FBE828A-4EB1-494B-8330-C5F110D91A71%40pebody.org<https://groups.google.com/d/msgid/google-code/4FBE828A-4EB1-494B-8330-C5F110D91A71%40pebody.org?utm_medium=email&utm_source=footer> > . > For more options, visit https://groups.google.com/d/optout. > -- Regards Vivek Dhiman -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CABaJBv%2BQWmn5ZcLvBWuC8k5Bw0%2Be5ALGxV5SjfcJEi9gKFS2Vw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
