techInterview Discussion 

A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor 
No really, heap is not just overkill (coding it might be easier) it is inefficient compared to just making one pass through it.
Instead of integers, suppose the objects in the array were big blogs of strings such that comparing them is inefficient...
Tapori Wednesday, June 20, 2007
Instead of maintaining a heap of size equal to array size, how about maintaining a heap(min) of size equal to k,here in this case k is 3.
Make one pass through the array and populate the heap accordingly such that k largest values seen so far are in the heap. At the end, the root of the heap is the kth largest element. I guess this will reduce the number of comparisions compared to maintiang k individual variables.
haresh Wednesday, June 20, 2007
There are better algorithms.
Heap is not really optimal. Best is to follow the "tournament" principle which is used to find the second largest (generalized to kth largest) Check this out: http://www.seeingwithc.org/topic3html.html
Tapori Wednesday, June 20, 2007
Keeping an array to keep largest K elements will work well till k is small. As k grows you might have complexity probems .It might become much higher then o(n).
Google for QuickSelect Algorithm on net . Its a variation of quick sort and is used specifically for this purpose as far as I know.
According to the Bible (CLR Intro to Algos any ith order statistic) can be found in O(N) worst time using some rather complex select and in expected
O(N) time using simpler randomized select which is relatively trivial to code. ith order statistic is ith smallest element but the algo can be adapted for the largest element.
Bytheway Saturday, June 23, 2007
Thank you Michael G: I was wondering about the solution to CLR problem 10.11: prove that the second smallest of n elements can be found with n + lg n  2 comparisons in the worst case.
Your use of priority queue gives me a hint.
Bytheway Saturday, June 23, 2007
"Is complexity of building a heap really O(n) ? Maciek"
When heap has N nodes inserting a new node is O(logN) So the time to build it is log0+log1+log2+... logN and I have not the lsigntest idea if that may end up being O(N). Any illumination appreciated.
Bytheway Saturday, June 23, 2007
OOps, again according to the Bible since each heap insertion takes O(logN), building the heap of N elements is O(NlogN) but the bound is not 'asymptotically tight'.
Tighter bound analysis on page 145 chapter 7.3 in my edition shows that heap can indeed be built from unordered array in O(N) time. Michael is right.
Bytheway Saturday, June 23, 2007
Bleah,
tournament principle is way too much to code in general kth case and the result is O(N) + O(logN)  const in any case. Not muche better than heap based alternative. Somebody got really confused at http://www.seeingwithc.org/topic3html.html as well. They have for a second tournament: 7 3 8 3 8 9 which is braindead. Should be: 7 3 8 7 8 8
Bytheway Sunday, June 24, 2007
Bytheway, having lazy programmers is not an excuse for having a crappy product.
Anyway, for k=3, the tournament is pretty good compared to the heap, does not matter is some website got it wrong. We all know finding 3rd largest is O(N). The constant factor is what matters.
Tapori Sunday, June 24, 2007 
Powered by FogBugz