0

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

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

一种方法是弹出 minheap 的顶部元素并将其推送到 maxheap 上。

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

这是我最终做的事情：

我实际上必须在 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];

(*)由于父母被降级为孩子，因此在上述步骤中已经有偿比较是一种浪费，但我认为这是不可避免的。

4

3 回答 3

2

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

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

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

于 2012-07-07T22:09:13.377 回答
0

使用 min-max-heap 或 treap 可能会为您提供最佳服务。min-max-heap 似乎是为你正在做的事情量身定做的，但是treaps 非常全面，它们也可能工作得很好——特别是如果你需要的不仅仅是查找最小值和最大值以及添加值。

http://en.wikipedia.org/wiki/Min-max_heap

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

于 2012-07-06T23:05:48.220 回答
-1

使用 min-max heap，它是一个双端优先级队列，你可以在 o(lgn) 中做这件事，你不能在小于 O(lgn) 的时间内做

但是您可以使用它们在 o(1) 中插入的分摊算法，例如斐波那契堆，

于 2012-07-06T19:25:24.937 回答