For finding top K elements using heap, which approach is better?
- NlogK, use Minheap of size K and remove the minimum element so top k elements remain in heap
- KlogN, use Maxheap, store all elements and then extract top K elements
I did some calculations and at no point, I see that NLogK better than KlogN.
N= 16 (2^4), k = 8 (2^3)
O(Nlog(K)) = 16* 3 = 48
O(Klog(N)) = 8 * 4 = 32
N= 16 (2^4), k = 12 (log to base 2 = 3.5849)
O(Nlog(K)) = 16* 3.5849 = 57.3584
O(Klog(N)) = 12 * 4 = 48
N= 256 (2^8), k = 4 (2^2)
O(Nlog(K)) = 256* 2 = 512
O(Klog(N)) = 4 * 8 = 32
N= 1048576 (2^20), k = 16 (2^4)
O(Nlog(K)) = 1048576* 4 = 4194304
O(Klog(N)) = 16 * 20 = 320
N= 1048576 (2^20), k = 1024 (2^10)
O(Nlog(K)) = 1048576* 10 = 10485760
O(Klog(N)) = 1024 * 20 = 20480
N= 1048576 (2^20), k = 524288 (2^19)
O(Nlog(K)) = 1048576* 19 = 19922944
O(Klog(N)) = 524288 * 20 = 10485760
I just wanted to confirm that my approach is correct and adding all elements to heap and extract top k elements is always the best approach. (and also simpler one)