从std :: heap的中间删除一个元素

Question

我正在使用优先级队列作为具有一个额外要求的调度程序.我需要能够取消预定的项目.这相当于从优先级队列的中间删除项目.

我无法使用std::priority_queue除了top之外的任何元素的访问受到保护.

我正在尝试使用algorithm堆函数.但我仍然错过了我需要的那件作品.当我从堆中间删除一个元素时,我希望它能够有效地重建它自己.C++提供了这些堆函数:

• std::make_heap O(3N)
• std::push_heap O(LG(n))的
• std::pop_heap O(2 lg(n))

我想要一个像std::repair_heap大O < 3n这样的新功能.我将它提供了取消项目所在的洞的位置,它将适当地调整堆.

不提供std::repair_heap功能似乎是一个巨大的疏忽.我错过了一些明显的东西吗

是否有提供符合stl标准的库std::repair_heap？

是否有更好的数据结构来建模调度程序？

注意:由于某些原因,
我没有使用std::map.

• 堆具有恒定的内存开销.
• 堆具有令人敬畏的缓存局部性.

Answer 1

我想你知道要删除的堆容器(索引n)中的哪个元素.

1. 设置值v[n] = BIG;的值BIG确实比堆中的任何其他值大.
2. 呼叫 std::push_heap( v.begin(), v.begin()+n+1 );
3. 呼叫 std::pop_heap( v.begin(), v.end() );
4. 呼叫 v.pop_back();
5. 完成

操作是O(ln(n))

RE:请求证明

首先,限定符:此方法假定std push_heap使用的算法.
具体来说,它假设std push_heap(v.begin(),v.begin()+ n + 1)只会改变
那些作为n的后代的元素的范围[0,n] ,即下面的集合中的索引:

A(n)={n,(n-1)/2,((n-1)/2-1)/2....0}.  

这是std push_heap的典型规范:

http://www.cplusplus.com/reference/algorithm/push_heap/ "给定堆范围[first,last-1],此函数通过将值放入(last)将扩展到的堆范围扩展到[first,last] -1)进入其对应的位置."

它是否保证使用您在教科书中阅读的"常规堆算法"？你告诉我.

无论如何,这里是你可以运行的代码,从经验上看,它是有效的.我正在使用VC 2005.

#include <algorithm>
#include <vector>
#include <iostream>

bool is_heap_valid(const std::vector<int> &vin)
{
    std::vector<int> v = vin;
    std::make_heap(v.begin(), v.end());
    return std::equal(vin.begin(), vin.end(), v.begin());
}


int _tmain(int argc, _TCHAR* argv[])
{
    srand(0);
    std::vector<int> v;
    for (int i=0; i<100; i++)
    {
        v.push_back( rand() % 0x7fff );
    }
    std::make_heap(v.begin(), v.end());

    bool bfail = false;
    while( v.size() >= 2)
    {
        int n = v.size()/2;
        v[n] = 0x7fffffff;
        std::push_heap(v.begin(), v.begin()+n+1);
        std::pop_heap(v.begin(), v.end());
        v.resize(v.size()-1);
        if (!is_heap_valid(v))
        {
            std::cout << "heap is not valid" << std::endl;
            bfail = true;
            break;
        }
    }
    if (!bfail)
        std::cout << "success" << std::endl;

    return 0;

}

但我有另一个问题,就是如何知道需要删除的索引"n".在使用std push_heap和std pop_heap时,我无法看到如何跟踪它(知道堆中的位置).我认为你需要编写自己的堆代码,并在每次在堆中移动对象时将堆中的索引写入对象.叹.

Answer 2

不幸的是，该标准缺少此功能（非常重要）。使用g ++，您可以使用非标准函数std::__adjust_heap来执行此操作，但是没有简便的可移植方式来执行此操作-并且__adjust_heap在不同版本的g ++中有所不同，因此您甚至无法在g ++版本上进行移植。