CareerCup

Max heap

I will use a linked list to store the incoming streams rather than a array. Because it need to have a fast insertion and deletion which is not possible with the array.

Above two are inefficient solutions.

if there are n numbers of which we need to find smallest first k elements, there is a solution to do this in O(n + k(log k)) if the final result should be sorted. if the final result doesn't need to be sorted then it can be done in O(n).

Refer to: http://en.wikipedia.org/wiki/Selection_algorithm

The two solutions below my post are both inefficient. Moreover, suarabhroongta2's solution is wrong and the solution using Max heap reduces to O(n log(k)).

@Augustine

Moreover,the selection algorithm provides a solution to the problem of finding the k-th smallest number in a list.

The problem being discussed *here* is different. Read it again.

@random: When we use a min heap, we don't know when to update the heap or just leave off the incoming number from the stream.
So we need to use a max heap of size "N".
Initially construct a MAX HEAP of the first "N" input numbers from the stream

updateheap(H, num) {
  if (H.GetRoot().GetValue() < num) return;
  H.DecreaseKey(H.GetRoot(), num);
}

Why not store in a binary search tree and output the contents in inorder tree traversal?

I had the same idea as Dumbo had,if we make use of binary tree to insert elements as they are coming, and later on go with inorder tree traversal.

I think the main problem here is with 'storage'. The selection algorithms expect you to have the entire list in memory and accessible. But the heap/array solution works 'on the fly'.

There are several parts of the question.
1) How to store the entire set of data?
Since there is no much requirement stated, we can simly use list or vector and add new item at the end.
2) How to get only the n smallest item?
A max heap or Binary search tree (BST)of size n will do the job. If total number of items is much larger than n it won't be efficient to keep all the items in max heap or BST. In stead keep only n smallest item in max heap or BST and then every time you get a new item you have to replace the max item with new item if it is greater and then rebuild the heap or BST. The time complexity will be log(n) in both cases.
3) Do you need the first n smallest items in sorted order?
Heap won't keep the items sorted whereas BST will do the job.

maintain a max heap of n number. if coming number is smaller than the maxm number swap the max with the incoming number and then build the heap gain to keep the max.