ekt_bear: I'm going to see a long stream of numbers. Say, N of them..think N=1 billion, 1 trillion, etc.

I want to store the top K largest of these numbers. Think K=10, etc.

Design a function/program that given stores the K largest numbers of this stream. Try to make your program/function as efficient as possible.

Hint: Essentially, start thinking about how to design a function insert(f) that given a number f, will check whether it needs to be stored in my collection of the K largest numbers and updates this collection appropriately.

/**PHCN has decided to abandon us, so i wrote this code from a mobile phone, if it works its my code else @ekt_bear wrote it  
***/
import java.util.*;
public class TopK
{
        //assuming k is 5
	int k=5; 
        int[] numbers;

	public TopK()
	{
		numbers = new int[k];
		for(int i=0; i< numbers.length; i++)
                {

                   numbers[i]=0;
                }
	}
	public void insert(int n)
	{
		//sort the arrays in ascending order
		Arrays.sort(numbers);
		for(int i=0; i<=numbers.length; i++)
                {
			if(n>numbers[i])
                            
                        numbers[i]=n;
                            break;      
                }
	}
        public void print()
        {
            for(int i=0; i<numbers.length; i++)
                    System.out.println(numbers[i]);
        }
          public static void main(String[] args)
          {
              TopK tp = new TopK();
              //Here you will read @ekt_bear 1 Zillion numbers and insert them individually e.g tp.insert(read.nextInt)
              //but for sake of convinience i will just insert some numbers to test it
               tp.insert(90);
               tp.insert(40);
               tp.insert(100);
               tp.insert(60);
               tp.insert(10);
               tp.insert(80);
               tp.insert(110);
               tp.insert(1000);
               tp.insert(260);
               tp.insert(10);
               tp.print();
          }

}

class Node
{
        private int iData;

        Node(int key)
        { iData = key; }

        int getKey()
        { return iData; }

        void setKey(int id)
        { iData = id; }
}
        class Heap
        {
            private Node[] heapArray;
            private int maxSize; // size of array
            private int currentSize; // number of nodes in array

        Heap(int mx) 
        {
            maxSize = mx;
            currentSize = 0;
            heapArray = new Node[maxSize];
            
            for(int i=0; i<heapArray.length; i++)
                {
                    Node newNode = new Node(0);
                     heapArray[i] = newNode;
                    currentSize++;              
                }    
        }

        boolean isEmpty()
        { return currentSize==0; }

        boolean insert(int key)
        {
            for(int i=0; i<heapArray.length; i++)
                {
                                          Node newNode = new Node(key);
                    while(newNode.getKey() > heapArray[i].getKey())   
                    {
                        Node temp = heapArray[i];
                        heapArray[i] = newNode;
                        change(i+1, temp.getKey());
                        trickleUp(i);
                        return true;    
                    }
                }
             return true;
        } 

        void trickleUp(int index)
        {
            int parent = (index-1) / 2;
            Node bottom = heapArray[index];
                while( index > 0 &&
                heapArray[parent].getKey() < bottom.getKey() )
                {
                    heapArray[index] = heapArray[parent]; // move it down
                    index = parent;
                    parent = (parent-1) / 2;
                } 
                heapArray[index] = bottom;
        } 
       
       public boolean change(int index, int newValue)
        {
            if(index<0 || index>=currentSize)
            return false;
            int oldValue = heapArray[index].getKey(); // remember old
            heapArray[index].setKey(newValue); // change to new
            if(oldValue < newValue) // if raised,
            trickleUp(index); // trickle it up
            return true;
        } 
        public void displayHeap()
        {
                for(int i=0; i<heapArray.length; i++)
            {
                System.out.println(heapArray[i].getKey());
            }
        } 
      
} 
class HeapApp
{
       public static void main(String[] args) 
       {
            Heap theHeap = new Heap(2); 
            theHeap.insert(7000000); 
            theHeap.insert(4000);
            theHeap.insert(50000);
            theHeap.insert(20);
            theHeap.insert(-1);
            theHeap.insert(100);
            theHeap.insert(8000);
            theHeap.insert(30);
            theHeap.insert(10);
            theHeap.insert(900000000);

            theHeap.displayHeap();
            
           
       }
}

ekt_bear: Why not use the java collections heap rather than implementing your own?

ekt_bear: What is "length of value?"

Like, what is the length of the value of say the number 50?

Javanian: @ekt_bear i'm sorry for the late reply there has been shortage of power in my area.

O.k. I tried implementing it with a BST it worked but it was no different from when i did it with a heap. It will take O(log₂n) time at worst case. Although i have to admit that suggesting a BST at first was wrong, what i had in mind was something like a Binary Heap which will return the maximum item in O(1) time at worst case. But it is more or less useless because I'm not going to be inserting all the items. So i wont be able to take advantage of this...