从头开始构建大小为 N 的二进制堆需要 NlogN 比较平均时间，因此需要线性时间。
鉴于两个大小为 N 的二进制堆已经就位，如何在线性时间内（使用线性比较次数）构造一个包含所有 2N 个键的单个二进制堆？
问问题
133 次
1 回答
5
从头开始构建大小为 N 的二进制堆需要 NlogN 比较平均时间，因此需要线性时间。
如果您的意思是“从大小为 N 的数组构造大小为 N 的二进制堆”，那么这不一定是正确的。您可以在线性时间内完成。请参阅在此处构建堆 。
因此，对于您的问题，如果您在两个数组中有两个堆，则连接数组并在结果数组上运行相同的算法将是线性的。
于 2014-07-23T10:30:53.667 回答