java - 在线性时间内从两个大小为 N 的二进制堆构造一个大小为 2N 的二进制堆？

Question

从头开始构建大小为 N 的二进制堆需要 NlogN 比较平均时间，因此需要线性时间。

鉴于两个大小为 N 的二进制堆已经就位，如何在线性时间内（使用线性比较次数）构造一个包含所有 2N 个键的单个二进制堆？

Answer 1

从头开始构建大小为 N 的二进制堆需要 NlogN 比较平均时间，因此需要线性时间。

如果您的意思是“从大小为 N 的数组构造大小为 N 的二进制堆”，那么这不一定是正确的。您可以在线性时间内完成。请参阅在此处构建堆 。

因此，对于您的问题，如果您在两个数组中有两个堆，则连接数组并在结果数组上运行相同的算法将是线性的。