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 | Max 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