0

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

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

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

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

4

1 回答 1

2

感谢 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 的指针。它基本上是大多数堆拥有的“信息字段”。

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

于 2020-01-02T18:59:52.573 回答