o（klogn）解是求第k个极小值的平凡解，这里O(klogk) time algorithm to find kth smallest element from a binary heap是o（klogk）解但我在想一个算法，如果正确的话可以是o（k）从最小堆中取出前k个元素（前k个节点，按级别遍历）并将其存储在数组中。现在，max heapify这个数组自下而上，这将花费o（k）时间。这个堆的根将是必需的答案。有人能看到这个算法中的缺陷吗？
最佳答案
考虑这个例子
1
2 11
3 4 12 13
如果你想得到3dmin元素，它就不在前3个节点中。
关于algorithm - O(k)算法从最小堆中查找第k个最小元素，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27000059/