Get K Max and Delete K Max in stream of incoming integers

Get K Max and Delete K Max in stream of Incoming Integers 

Solution 1 : Using Min Heap

Algorithm :

1) Keep a Min & Max Heap of K size
2) Store first K elements in them.
3) If a new element comes with smaller or larger than root then reorder   heap.

Example : 

Min heap	Min heap

Complexity :
-O(1) for search First Minimum/Maximum.
-To get second Min/Max we need to Delete Min/Max element reordering takes O(log N) and again we can Find second Min/Max in O(1).
- To insert new Min/Max element takes O(log N)

Solution 2: Using Linked List or Queue.

Example :

Algorithm

Whenever new number x comes, check 

  if x < head -> data than  (in case of 0 here)
        create node Temp
        Temp->next = head 
        Temp = Head.
        remove rear (to keep K size constant)
  else of  x < rear -> data than (in case of 2 here)

      create new Temp node
      traverse link list and put Temp at appropriate node (insert)
      remove rear (to keep K size constant)

Same solution can be applied for K Max

Time Complexity
O(1) To get Min/Max
O(K) To get K Min/Max
O(K) To reorder at each time.

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE