我有一个最大堆和一个最小堆,其中最大堆的最大元素小于或等于最小堆的最小元素。
我现在想移动最小堆的最小元素成为最大堆的最大元素。
一种方法是弹出最小堆的顶部元素并将其插入最大堆。
有没有更有效的方法来做到这一点?
这是我最终做的:
我实际上不得不将一个元素插入到 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 ,但我认为这是不可避免的。
最佳答案
当您知道要插入的元素小于/大于最小/最大元素时,您真正需要的是一种插入优先级队列的有效方法,具体取决于这是最小堆还是最大堆。对于传统的“堆”数据结构,这需要 O(log n) 时间。
但是如果您愿意为您的优先级队列使用与传统“堆”数据结构不同的表示,那么这样的插入可以很容易地在 O(1) 时间内运行。许多不同类型的优先级队列都可以做到这一点,例如左堆、倾斜堆或配对堆。
编辑:当然,您仍然需要支付从原始优先级队列中移除的成本,无论如何这可能是 O(log n),尽管也有一些方法可能对此有所帮助,例如“延迟删除”。
关于c++ - 将 minheap.top 移动到 maxheap.top,其中 maxheap.top <= minheap.top,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11368437/