我目前正在创建一个源代码，以将满足最小堆属性和完整二叉树的形状不变性的两个堆组合起来。但是，我不确定我正在做的是否是合并两个堆的正确接受方法，以满足我提出的要求。
这是我的想法:
给定两个表示为最小堆的优先级队列，我将第二棵树的节点逐个插入到第一棵树中并修复堆属性。然后我继续此操作，直到第二棵树中的所有节点都位于第一棵树中。
据我所知，这感觉像是一个 nlogn 算法，因为我必须遍历第二棵树中的所有元素，并且每次插入都需要大约 logn 时间，因为完整二叉树的高度最多为 logn..但我认为有一种更快的方法，但我不确定还有什么其他可能的方法。
我想我可以插入整个树，但这会破坏形状不变性和顺序不变性..我的方法是唯一的方法吗？
最佳答案
事实上，在线性时间和标准函数中构建堆是可能的 std::make_heap保证线性时间。该方法在维基百科关于 binary heap 的文章中进行了解释。 .
这意味着您可以通过在包含两个堆中的元素的范围上调用 std::make_heap 来简单地合并堆。如果堆大小相似，这是渐近最优的。可能有一种方法可以利用预先存在的结构来减少常数因子，但我发现这不太可能。
关于c++ - 这就是我将两个最小堆组合在一起的方式吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/29200187/