@Don: Nope. Constructing a heap can be done in O(n). See, e.g.,
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
.
Dave
On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:
> Constructing a max-heap is O(n*log n)
>
> However, the problem asked for a solution using tournament method.
> If you ignore that requirement, an O(n) solution is trivial, and
> doesn't require the additional storage of a heap:
>
> int first = max(A[0], A[1]);
> int second = min(A[0], A[1]);
> for(i = 2; i < N; ++i)
> {
> if (A[i] >= first)
> {
> second = first;
> first = A[i];
> }
> else if (A[i] > second)
> second = A[i];
> }
>
> // First and second now contain 1st and 2nd largest values in A
>
> Don
>
> On Sep 3, 5:04 am, bharat b <[email protected]> wrote:
> > Construct a max-heap --> O(n)..
> > call delete() 2 times .. --> O(logn)..
> > ===> O(n) time..
> >
> >
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/bKzs-wHLSoIJ.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
