我有一个包含n元素的最小堆H。该函数min(H,k)按从小到大的顺序打印k最小值。在方法的末尾，H仍包含n值。我被要求在O(klogk)中给出min(H,k)算法并O(k)额外的空间。在解决方案中，他们执行以下操作：
我们将使用一个额外的最小堆T没有任何数据。它将包含原始最小堆H元素的副本(H和T的值之间将有一个双向指针(。算法：
- 在
O(1)中打印H的最小元素。 - 将根的两个子项插入
TH。 - 只要我们不打印 k 值就可以：
- 打印
T的最小元素(我们称之为x(。 - 从
T中删除x。 - 将堆
Hx的两个子项插入堆T(如果存在(。
- 打印
我不明白为什么这个算法是有效的，最糟糕的是，我根本不了解算法。我知道我们创建了一个新的堆T.我也明白为什么打印H的最小元素是O(1).我不明白"插入TH根的两个孩子"部分。它是否将这些子项的指针插入堆T或仅插入其值？如果答案是第二个选项，那么我怎么知道要遵循下一个选项？
T的元素必须让你了解元素和元素在原始堆中的位置。 如果你能做到这一点，那么你可以找到下一个元素，你可以找到值。
各种表示形式将起作用。 例如，对于最小堆数组表示形式，您需要知道的只是数组中的偏移量，以及数组长度和数组开头的全局常量。
关于为什么这样做的关键见解是，T上的所有操作都是大小为O(k)的堆上的堆操作。 因此，他们每个人都采取O(log(k)). 需要O(k)操作，因此结果O(k log(k))。