@elmirap Thanks for the sharing those. I'm still trying to fully understand this.
Assuming we a stream of key val pairs: thinking about using a heap.
Are you removing the elements from the heap? I thought its just returning values of the top K stocks. Is even returning top K from heap is O(klogn)?
Secondly I thought "heapify" is O(n)  you wrote O(log n) < I think O(log n) is for inserting into a existing heap. And heapify is building a heap from scratch.
Inserting into a heap is O(log n). What is the final datastructure being used here? Sorry python user here..
Please correct me if I am wrong.
Stock Ticker


Here is my solution. I used a HashMap in conjunction with quickselection.
 Inserting a stock is O(n)
 Updating a stock is O(1)
 Getting top k stocks (not in sorted order) is O(n) average case
public class StockTicker { public class Stock{ String sym; double price; public Stock(String s, double val){ this.sym = s; this.price = val; } } HashMap<String,Stock> st; HashMap<String,Integer> ind; int unique; int max; Stock[] stocks; public StockTicker(int k){ this.unique = 0; this.max = k; this.st = new HashMap<String, Stock>(); this.ind = new HashMap<String, Integer>(); this.stocks = new Stock[k]; } public void addOrUpdate(String sym, double price){ if(!st.containsKey(sym)){ Stock stock = new Stock(sym,price); st.put(sym, stock); ind.put(sym, unique); stocks[unique++] = stock; } else{ Stock update = st.get(sym); update.price = price; } } public List<Stock> top(int k){ List<Stock> res = new ArrayList<Stock>(); Stock[] temp = new Stock[max]; for(int i = 0; i < temp.length; i++){ temp[i] = new Stock(stocks[i].sym, stocks[i].price); } int top = quickselect(temp, 0, temp.length1, k); for(int i = 0; i <= top; i++){ res.add(temp[i]); } return res; } public int quickselect(Stock[] stocks, int left, int right, int kth){ if(left == right){ return left; } int split = partition(stocks, left,right); if(kth1 == split){ return split;} else if(kth1 > split){ return quickselect(stocks,split + 1, right, kth);} else { return quickselect(stocks, left , split1, kth);} } public int partition(Stock[] stocks, int left, int right){ int lastIndex = right; double pivot = stocks[lastIndex].price; while(left <= right){ while( left <= right && stocks[left].price > pivot ){ left++; } while( left <= right && stocks[right].price <= pivot){ right; } if(left <= right && stocks[left].price <= pivot && stocks[right].price > pivot){ swap(stocks,left,right); } } swap(stocks,left,lastIndex); return left; } public void swap(Stock[] stocks, int x, int y){ Stock eleX = stocks[x]; Stock eleY = stocks[y]; stocks[x] = eleY; stocks[y] = eleX; } public Stock getStock(String sym){ return st.get(sym); } } '''