这是我将两个最小堆组合在一起的方式吗？
Is this how I combine two min-heaps together?
我目前正在创建一个源代码，以将满足最小堆 属性 的两个堆与完全二叉树的形状不变性结合起来。但是，我不确定我正在做的是否是合并满足我提出的要求的两个堆的正确接受方法。
这是我的想法：
给定两个表示为最小堆的优先级队列，我将第二棵树的节点一个一个地插入到第一棵树中并固定堆 属性。然后我继续这样做，直到第二棵树中的所有节点都在第一棵树中。
据我所知，这感觉像是一个 nlogn 算法，因为我必须遍历第二棵树中的所有元素，并且每次插入都需要大约 logn 时间，因为完整二叉树的高度最多为 logn .. 但我认为有一种更快的方法，但是我不确定还有什么其他可能的方法。
我在想我可以直接插入整棵树，但这打破了形状不变和顺序不变..我的方法是唯一的方法吗？
事实上，在线性时间和标准函数中构建堆是可能的 std::make_heap guarantees linear time. The method is explained in Wikipedia article about binary heap。
这意味着您可以通过在包含来自两个堆的元素的范围上调用 std::make_heap 来简单地合并堆。如果堆的大小相似，这是渐近最优的。可能有一种方法可以利用预先存在的结构来减少常数因子，但我发现这不太可能。
我目前正在创建一个源代码，以将满足最小堆 属性 的两个堆与完全二叉树的形状不变性结合起来。但是，我不确定我正在做的是否是合并满足我提出的要求的两个堆的正确接受方法。
这是我的想法：
给定两个表示为最小堆的优先级队列，我将第二棵树的节点一个一个地插入到第一棵树中并固定堆 属性。然后我继续这样做，直到第二棵树中的所有节点都在第一棵树中。
据我所知，这感觉像是一个 nlogn 算法，因为我必须遍历第二棵树中的所有元素，并且每次插入都需要大约 logn 时间，因为完整二叉树的高度最多为 logn .. 但我认为有一种更快的方法，但是我不确定还有什么其他可能的方法。
我在想我可以直接插入整棵树，但这打破了形状不变和顺序不变..我的方法是唯一的方法吗？
事实上，在线性时间和标准函数中构建堆是可能的 std::make_heap guarantees linear time. The method is explained in Wikipedia article about binary heap。
这意味着您可以通过在包含来自两个堆的元素的范围上调用 std::make_heap 来简单地合并堆。如果堆的大小相似，这是渐近最优的。可能有一种方法可以利用预先存在的结构来减少常数因子，但我发现这不太可能。