On 12/07/11 16:15, bittu wrote:
John You Can Use MinHeap
here is the algo
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of
the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]),
compare it with root of MH.
a) If the element is greater than t
John You Can Use MinHeap
here is the algo
1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of
the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]),
compare it with root of MH.
a) If the element is greater than the root then make it root and call
@John: It seems that a heap size of N would do the trick.
Dave
On Jul 11, 6:11 am, John Reid wrote:
> On 11/07/11 12:07, abhijith reddy wrote:
>
> > Wouldn't a heap be ideal for this ?
>
> I thought it might. Do I just need to limit the heap to size 2 * N to
> avoid storing values I'll never nee
use a heap u ill be using a min heap ie the Nth element will be the root.So
when u find a element compare with the root if its greater then replace the
root with this new number and call heapify function
On Mon, Jul 11, 2011 at 4:43 PM, abhijith reddy wrote:
> You can use priority_queue in STL. T
You can use priority_queue in STL. The size needs to be limited to N
elements. At any point the the N elements in the heap will give the largest
N
elements processed so far.
On Mon, Jul 11, 2011 at 4:41 PM, John Reid wrote:
>
>
> On 11/07/11 12:07, abhijith reddy wrote:
>
>> Wouldn't a heap be id
On 11/07/11 12:07, abhijith reddy wrote:
Wouldn't a heap be ideal for this ?
I thought it might. Do I just need to limit the heap to size 2 * N to
avoid storing values I'll never need?
Thanks,
John.
On Mon, Jul 11, 2011 at 3:35 PM, John Reid
mailto:j.r...@mail.cryst.bbk.ac.uk>> wrote: