我将优先级队列用作调度程序，但有一个额外的要求。我需要能够取消预定的物品。这等于从优先级队列的中间删除一个项目。
我不能使用std::priority_queue，因为对top以外的任何元素的访问都受到保护。
我正在尝试使用algorithm的堆函数。但是我仍然缺少我需要的东西。当我从堆中间删除一个元素时，我希望它能够高效地重建自身。 C ++提供了这些堆函数：
std::make_heap O（3n）std::push_heap O（lg（n））std::pop_heap O（2 lg（n））我想要一个带有大O <3n的新功能，例如std::repair_heap。我将为它提供孔的位置，该位置曾是被取消项目的位置，它可以适当地调整堆。
似乎不提供std::repair_heap功能是一个巨大的疏忽。我是否缺少明显的东西？
是否有提供符合stl的std::repair_heap的库？
是否有用于建模调度程序的更好的数据结构？
NOTE：由于某些原因，我没有使用std::map。
不幸的是，该标准缺少此（相当重要的）功能。使用g ++，您可以使用非标准函数std::__adjust_heap来执行此操作，但是没有简便的可移植方式来执行此操作-并且__adjust_heap在不同版本的g ++中略有不同，因此您甚至无法执行此操作可移植到g ++版本。
我想您知道要删除堆容器（索引n）中的哪个元素。
v[n] = BIG;的值BIG实际上大于堆中的任何其他值。std::push_heap( v.begin(), v.begin()+n+1 );std::pop_heap( v.begin(), v.end() );v.pop_back();运算是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时如何跟踪（知道堆中的位置）。我认为您需要编写自己的堆代码，并在每次将对象移动到堆中时将堆中的索引写入对象。叹气。
[您的repair_heap()如何工作？这是我的猜测：
如果您的堆是由某个迭代器范围定义的，请说（heapBegin，heapEnd）。您要删除的元素是堆的某个子树的根，该子树由某个子范围（subHeapBegin，subHeapEnd）定义。使用std::pop_heap(subHeapBegin, subHeapEnd)，然后使用subHeapEnd != heapEnd交换*(subHeapEnd-1)和*(heapEnd-1)的值，这会将已删除的项目放在堆容器的末尾。现在，您必须在子堆中的*（subHeapEnd-1）处向上渗透元素。如果我没有错过任何可能的事情，那么剩下的就是从堆容器中砍掉end元素。
在尝试正确编码之前（我已经跳过了一些细节，例如计算subHeapBegin和subHeapEnd），在进行麻烦之前，我会进行一些测试以确定make_heap()是否真的使您减速。 Big-O很有用，但它与实际执行时间不同。
在我看来，从堆中间删除可能意味着必须重建整个堆：之所以没有repair_heap的原因是，它必须执行与make_heap相同的工作（大哦）。 >
您是否可以执行将std::pair<bool, Item>放入堆中的操作，而只是使项目无效而不是删除它们？然后，当他们最终到达顶部时，只需忽略该项目并继续前进即可。
您可以尝试将“ std :: multiset”实现为堆结构并支持“ std :: erase”操作，因此您可以“ std :: find”该元素然后将其擦除。
这里有一些我用来从堆中删除项目的delphi代码。我不知道您所说的C ++没有修复功能，但是。.]]
首先流行，因此您了解事物的工作原理：