c++ - 从 std::heap 中间移除一个元素

Question

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

我不能使用 std::priority_queue 因为对除 top 之外的任何元素的访问是 protected 。

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

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

我想要一个像 std::repair_heap 这样的新函数，带有一个 big-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 ) 只会改变范围 [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/ “给定一个堆范围 [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 时，我看不到如何跟踪它(知道堆中的位置)。我认为每次对象在堆中移动时，您都需要编写自己的堆代码并将堆中的索引写入对象。叹息。