algorithm - 在线性时间内查找堆中小于 k 的所有数字

Question

给定一个堆，以及堆中的某个数 k，如何在 O(r) 中找到比 k 小的 r 个数？

有人给了我一个我不明白的算法:在堆上进行预购，当值小于 k(和 != null)时打印它们。据推测这需要 O(3r+1)=O(r) 检查。

有人可以向我解释解决方案吗？谢谢!

Answer 1

您需要在堆上访问的唯一数字是小于 k 的数字及其直接子代。一旦你看到一个太大的 child ，你就知道你不需要看它的 child 。堆中的每个数字最多有两个 child ，因此这对您访问的不需要的数字施加了大约 2r 的限制(显然 r=0 是一种特殊情况)。