如果我将数据点保存在minheap（a）中，我的应用程序效率最高。但是，作为结束步骤，我想从a输出topk。
作为起点，将数据点从a从后到前添加到另一个minheap（B），并且一旦填充了K个数据点，reject datapoints小于根将以相反的顺序提供TopK列表。
我想知道是否需要从后到前完全遍历一个，或者当我处理完至少提供了k个数据点的行（即树深度）时，是否可以停止？
我知道有一些算法可以将minheap转换为maxheap，但我不希望对原始堆进行排序，只希望对TopK进行排序。
提前谢谢
最佳答案
您需要考虑底部的log 2（k）完整行。然后你可以停止，因为每一个比它更接近根的项都小于k或者更多的其他项，并且不能在前k。
这并不能帮你节省很多工作，因为堆里至少有一半的东西是树叶。