c++ - 将 minheap.top 移动到 maxheap.top，其中 maxheap.top <= minheap.top

Question

我有一个最大堆和一个最小堆，其中最大堆的最大元素小于或等于最小堆的最小元素。

我现在想移动最小堆的最小元素成为最大堆的最大元素。

一种方法是弹出最小堆的顶部元素并将其插入最大堆。

有没有更有效的方法来做到这一点？

这是我最终做的:

我实际上不得不将一个元素插入到 minheap 中，然后执行上述操作，我做了以下操作:

// place value to insert at end of minheap
mintoph[mintoph_size] = R;

// use std::pop_heap, minimum element now at end
pop_heap(mintoph.begin(), mintoph.begin() + mintoph_size + 1, greater<int>());

// (*) make room in maxheap at top
for (int pos = maxboth_size++; pos > 0;)
{
    int parent = (pos - 1) / 2;
    maxboth[pos] = maxboth[parent];
    pos = parent;
}

// move element from back of minheap to maxheap head
maxboth[0] = mintoph[mintoph_size];

在上面的步骤 (*) 中，已经付费的比较是一种浪费，因为 parent 被降级为 child ，但我认为这是不可避免的。

Answer 1

当您知道要插入的元素小于/大于最小/最大元素时，您真正需要的是一种插入优先级队列的有效方法，具体取决于这是最小堆还是最大堆。对于传统的“堆”数据结构，这需要 O(log n) 时间。

但是如果您愿意为您的优先级队列使用与传统“堆”数据结构不同的表示，那么这样的插入可以很容易地在 O(1) 时间内运行。许多不同类型的优先级队列都可以做到这一点，例如左堆、倾斜堆或配对堆。

编辑:当然，您仍然需要支付从原始优先级队列中移除的成本，无论如何这可能是 O(log n)，尽管也有一些方法可能对此有所帮助，例如“延迟删除”。