在树中找到最大的 n 个节点的算法

Question

假设我们有一棵树，其节点包含一些数字。我需要在这棵树中找到 n 个最大的数字。我脑子里有两个算法:

1. 使用 BFS 或 DFS 遍历树并将其节点放入数组中，然后使用快速排序对其进行排序并返回 n 个第一个元素。此方法的时间复杂度为 O(|V| + |E| + |V|log|V|)，空间复杂度为 O(|V|)

2. 其次是迭代树找到最大元素并标记它 n 次。所以时间复杂度是 O(N*(|V| + |E|))，空间复杂度也是 O(|V|)。

哪个解决方案更好，也许我走错了路，还有更好的解决方案吗？

Answer 1

还有一个标准heap选择算法不起作用？

基本算法是(假设k是你要选择的项目数)

create an empty min-heap
for each node (depth-first search)
    if heap.count < k
        heap.Add(node)
    else if node.Value < heap.Peek.Value()
        heap.RemoveSmallest()
        heap.Add(node)

for 循环完成后，您的堆将包含 k 个最大值。您可以通过以下方式按升序获取它们:

while heap.count > 0
    output (heap.RemoveSmallest().Value)

如果想升序排列，就按照上面的方法从堆中取出，放到一个数组中，然后反转数组即可。

这个算法是 O(n log k)，其中 n 是树中的节点数，k 是你想要的项目数。