CareerCup

Keep a max-heap of size K, if a value is smaller than the largest value in the max-heap then pop the largest value from the max-heap and insert the new value.
N * log(K)

An O(n) solution is to use linear selection algorithm to find (k+1)st order statistic [ie (k+1)st min element]. All elements to the left of the index - k+1 in the partitioned array are the k minimum elements.

Modify the quick sort algorithm.

Since all the elements less than pivot will be on the left and more will be on right, keep calling partition() method until it partition the array at kth index.

Here is the algo-

If k = pivot
		return pivot //all values before pivot is your ans

	if k < pivot. 
		partition(begin, k-1, array) //answer lies in left partition

	if k > pivot. 
		partition(k+1, end, array) //answer lies in right partition

Worst case complexity will be same as Quick sort.
But average case when each time array is divided into two parts, number of comparisons will be
n + n/2 + n/4 + n/8 +...... = 2n

Hence O(n).

can't we sort it? O(nlogn)

#include<stdio.h>
#include<conio.h>

int main()
{
int *p,*visit;
int ele,i,j=0,k=0,temp=0;

printf("\nHow many elements ?? ");
scanf("%d",&ele);

printf("\nEnter elements : ");
p=(int *)malloc(sizeof(int)*ele);
//visit=(int *)malloc(sizeof(int)*ele);
for(i=0;i<ele;i++)
{
scanf("%d",&p[i]);
//visit[i]=0;

}


for(i=0;i<ele;i++)
{
for(j=0;j<ele-(i+1);j++)
{
if(p[j] > p[j+1])
{
temp=p[j];
p[j]=p[j+1];
p[j+1]=temp;
}
}
}

printf("\nSorted data is : ");

for(i=0;i<ele;i++)
printf("%d\t",p[i]);

printf("\nHow many minimum values you need ? ");
scanf("%d",&k);

printf("\nMiminum number of elements are : ");
for(i=0;i<k;i++)
printf("%d\t",p[i]);
//for(i=0;i<ele;i++)
// printf("\t%d",p[i]);

getch();
return 0;
}

Max heap implementation --

import java.util.Comparator;
import java.util.PriorityQueue;

% MaxHeap
class maxHeap implements Comparator<Integer> {
  public int compare(Integer n, Integer m){
		return (m-n);
	}
}

public class KSmallestNumbers {
	public static void main(String[] arg) {
		Comparator<Integer> cmp = new maxHeap();
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(3,cmp);

    % Input array
    Integer[] arr = {10,2,34,455,12,34,567,123,454,677,120,356,124};
    
    % Build heap.
		int i=1;
		for(Integer num:arr){
			if(i<=3){
				q.add(num);
			} else {
				if(num < q.peek()){
					q.poll();
					q.add(num);
				}
			}
			i++;
		}

    % Print the contents of the heap.
		for(Integer num:q){
			System.out.println(num);
		}
	}
}