algorithm - 如何实现一种算法以在 O (k) 时间内合并两个具有 n=2^k 个元素的堆？

Question

但是，我什至不知道这个问题意味着什么。

这只需要最少 O (n) 的时间来合并两个排序的数组，我不知道如何在 O (k) 时间内合并。

这总共有三个与之相关的问题：

这个问题的目的是探索以自上而下的方式高效构建标准堆的可能性。

1. 给出合并两个标准堆的算法的高级描述，每个标准堆都包含 n = 2^k 个元素。该算法应该在 O(k) 时间内运行。

2. 使用第 1 部分中指定的子例程，给出构建 2^n 个元素的堆的递归或迭代算法。

3. 写下第 2 部分中指定的算法的运行时间方程，求解。

Answer 1

您可以使用Binomial_heap或Leftist heaps。

当 n=2^k 时，它们都在 O(k) 时间内进行合并操作。