You can keep track of the median of an array as you put elements into it using a max heap and a min heap:
Start off with an empty min heap and max heap. For each element: * If the max heap is empty, or if your element is less than the max of the max heap, insert your element into the max heap. Otherwise, insert your element into the min heap. * If the min heap now has more elements than the max heap, pop the min from the min heap and insert it into the max heap. * If the max heap now has 2 more elements than the min heap, pop the max from the max heap and insert it into the min heap. Then, at every stage, if the max heap has more elements than the min heap, the median is at the top of the max heap. Otherwise it is halfway between the top of the max heap and the top of the min heap. Sent from my iPad > On 27 Mar 2014, at 17:53, Luke Pebody <[email protected]> wrote: > > The only way to get the nth element from a min heap is to "pop the top" n > times. This is O(n). > > Not sure what you are looking for otherwise. > > Maybe it's this: > > To find the kth smallest element using a max heap: > > Put the first k elements in the heap. > Now, for each remaining element, put it into the heap, and pop the maximum. > At all stages, the elements in the heap will be the k smallest elements you > have seen so far. Thus, at the end, the k'th smallest element will be the max > of the heap. > > Sent from my iPad > >> On 27 Mar 2014, at 17:38, vivek dhiman <[email protected]> wrote: >> >> 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. >>>> 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. >>> 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. -- 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/2F12F561-7F2F-458E-B81E-2ABFC0521DC4%40pebody.org. For more options, visit https://groups.google.com/d/optout.
