要使用堆查找前 K 个元素，哪种方法更好 - NlogK 或 KLogN？

Question

对于使用堆查找前 K 个元素，哪种方法更好？

NlogK，使用大小为 K 的 Minheap 并删除最小元素，使前 k 个元素保留在堆中
KlogN，使用Maxheap，存储所有元素，然后提取top K个元素

我做了一些计算，但我发现 NLogK 完全没有 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

我只是想确认我的方法是正确的，将所有元素添加到堆中并提取前 k 个元素始终是最好的方法。（还有更简单的）

Answer 1

I did some calculations and at no point, I see that NLogK better than KlogN.

因为 K <= N，NlogK 将始终大于或等于 KlogN。

这并不意味着，最小堆方法将比最大堆方法花费更多时间。

需要考虑以下，

在最小堆方法中，只有当下一个值大于头部时，我们才会更新堆。如果数组是升序，我们将执行 (N-K) 次，如果是降序，我们根本不会更新它。平均而言，树更新的次数比 N 少很多。
在Max堆中，需要堆化大小为N的树。如果K相对于N小到可以忽略不计，那么这个时候就可以成为主导因素。而在最小堆的情况下，heapify 作用于较小的 K 集。同样如第 1 点所述，N 的大部分值不会触发树的更新。

我写了一个小程序来比较这两种方法。来源可以访问here.

0 到 1M 数组随机排序的结果如下：

Test for Array size: 1000000

k         MinHeapIterations   MinHeapTime(ms)     MaxHeapTime(ms)     MaxTime/MinTime     
1         15                  6.07                72.03               11.88               
10        114                 3.85                70.09               18.19               
100       913                 4.11                69.60               16.93               
1000      6874                5.32                72.94               13.71               
10000     46123               16.52               79.89               4.83                
100000    230385              78.19               132.27              1.69                
1000000   0                   35.86               453.57              12.65

如您所见，

对于所有 K 值，最小堆确实优于最大堆
最小堆的树更新次数 (MinHeapIterations) 远小于 (N-K)

要使用堆查找前 K 个元素，哪种方法更好 - NlogK 或 KLogN？

For finding top K elements using heap, which approach is better - NlogK or KLogN?

heap

priority-queue