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

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

我不能使用std::priority_queue因为对除顶部之外的任何元素的访问都受到保护。

我正在尝试使用algorithm的堆函数。但我仍然缺少我需要的那部分。当我从堆中间删除一个元素时，我希望它能够有效地重建自身。 C++ 提供了这些堆函数：

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

我想要一个新功能，例如std::repair_heap带有一个大O 3n。我会向它提供被取消的项目曾经驻留的孔的位置，并且它会正确调整堆。

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

是否有提供符合 stl 的库std::repair_heap?

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

NOTE:
我没有使用std::map出于几个原因。

• 堆具有恒定的内存开销。
• 堆具有很棒的缓存局部性。

我猜您知道要删除堆容器（索引 n）中的哪个元素。

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

运算复杂度为 O(ln(n))

RE: 要求提供证明

首先，预选赛： 此方法假设了有关 std push_heap 使用的算法的一些信息。
具体来说，它假设 std push_heap( v.begin(), v.begin()+n+1 ) 只会改变范围 [0, n]
对于那些作为 n 的上升元素的元素，即以下集合中的索引：

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

以下是 std Push_heap 的典型规范：

http://www.cplusplus.com/reference/algorithm/push_heap/ http://www.cplusplus.com/reference/algorithm/push_heap/“给定一个堆范围 [first,last-1)，此函数通过将 (last-1) 中的值放入其相应位置，将堆范围扩展到 [first,last)。”

它保证使用您在教科书中读到的“正常堆算法”吗？ 你告诉我。

无论如何，这是您可以运行并根据经验查看它是否有效的代码。 我用的是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 时跟踪它（知道堆中的位置）。我认为你需要编写自己的堆代码，并在每次在堆中移动对象时将堆中的索引写入到该对象中。叹。