在O（K * log（K））中打印给定堆中最大的K个元素？

在O（K * log（K））中打印给定堆中最大的K个元素？

在最大堆中这是可能的，因为您仅从树中打印元素，而不提取它们。

首先确定最大元素，该元素位于根节点。形成一个指向节点的指针，并将其添加到否则为空的“最大”列表中。然后，对于每个

k

值，循环执行以下步骤。

• 从列表中d出最大元素，取O（1）。
• 打印其值，取O（1）。
• 将这个最大元素的每个孩子插入列表。插入它们时要保持排序，花费O（log（list的大小））时间。由于我们要执行k次此循环，因此此列表的最大大小为branch-size * k。因此，此步骤需要O（log（k））时间。

因此，根据需要，总的运行时间为O（klog（k））。