将二叉树转换为排序的键数组的最有效方法是什么？

Question

假设我们有一个单树二叉堆，二叉树的秩为 r，因此持有 2^r 个键。使用树的 k 个最小键将其转换为 k<2^r 长度排序数组的最有效方法是什么？假设我们只能使用惰性二项式堆和二项式树以外的任何其他数据结构。请注意，在每个级别上，子项都按顺序不必要地链接在一起，因此您可能不得不在某些时候进行一些比较。

我的解决方案是（假设 1<=k<=2^r）：

创建一个新的空惰性二项式堆 H。
将根的密钥插入堆中。
创建一个新的计数器 x，并设置 x=1。
对于每个级别 i=0,1,...（其中根在级别 0）：
- 令 c 为级别 i 的节点数。
- 设 x=x+c。
- 遍历级别 i 中的节点并：
  - 将每个节点 N 插入到 H。（在 O(1) 中）
  - 如果 x < k，递归地对每个节点 N 进行相同的处理，通过 x 以便继续计数。
重复k次：
- 从堆中提取最小键并将其放入输出数组。
- 从堆中删除最小密钥。（摊余成本：O(1)）
Return 输出数组。

伪代码中可能有一些漏洞，但我认为这个想法本身很清楚。我也设法实现了它。但是，我不确定这是完成此任务的最有效算法。

Answer 1

感谢 Gene 的评论，我发现我之前建议的算法并不总是有效，因为它假设 x 层的最大节点小于 x-1 层的最小节点，这不是一个合理的假设。

但是，我相信这个可以有效地完成工作：

public static int[] kMin(FibonacciHeap H, int k) {
    if (H == null || H.isEmpty() || k <= 0)
        return new int[0];
    HeapNode tree = H.findMin();
    int rank = tree.getRank();
    int size = H.size();
    size = (int) Math.min(size, Math.pow(2, rank));
    if (k > size)
        k = size;
    int[] result = new int[k];
    FibonacciHeap heap = new FibonacciHeap();
    HeapNode next = H.findMin();

    for(int i = 0; i < k; i++) { // k iterations
        if(next != null)
            for (Iterator<HeapNode> iter = next.iterator(); iter.hasNext(); ) { // rank nCr next.getParent().getRank() iterations.
                next = iter.next();
                HeapNode node = heap.insert(next.getKey()); // O(1)
                node.setFreePointer(next);
            }
        next = heap.findMin().getFreePointer();
        result[i] = next.getKey();
        heap.deleteMin(); // O(log n) amortized cost.
        next = next.child;
    }

    return result;
}

"freePointer"是HeapNode中的一个字段，我可以在其中存储指向另一个HeapNode的指针。它基本上是 "info field" 大多数堆。

设 r 为树的等级。每次迭代我们最多将 r 个项目插入外部堆。此外，每次迭代我们都使用 Delete-Min 从堆中删除一项。因此，插入的总成本为O(kr)，而Delete-Min的总成本为O(k*log(k)+k*log(r))。所以一切的总成本变成O(k(log(k)+r))

将二叉树转换为排序的键数组的最有效方法是什么？

What's the most efficient way to convert a binomial tree into a sorted array of keys?

sorting

algorithm

data-structures

binomial-heap