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

Question

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

现在，我希望将min堆的最小元素移动为max堆的最大元素。

要做到这一点，一种方法是弹出min堆的顶部元素并将其推到max堆上。

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

，这是我最后做的

实际上，我必须在min堆中插入一个元素，然后执行上面描述的操作，我执行了以下操作：

// 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];

由于父母被降职为孩子，这是对已经付费的比较的浪费，但我认为这是不可避免的。

Answer 1

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

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

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

Answer 2

你最好用一个最小的堆或者踏板来服务。minimums堆看起来是为你正在做的事情量身定做的，但是踏步是如此的全面，以至于它们也可能运行得很好--尤其是当你需要的不仅仅是查找最小值、最大值和附加值的时候。

heap

http://en.wikipedia.org/wiki/Treap

Answer 3

使用max堆，它是一个双端优先级队列，您可以在o(lgn)中完成这个任务，不能在小于O(lgn)的情况下执行。

但是您可以使用它们在o(1)中插入的摊销算法，比如fibonacci堆，