我猜您知道要删除堆容器（索引 n）中的哪个元素。
- 设置值
v[n] = BIG;价值BIG确实比堆中的任何其他值都大。
- Call
std::push_heap( v.begin(), v.begin()+n+1 );
- Call
std::pop_heap( v.begin(), v.end() );
- Call
v.pop_back();
- 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 时跟踪它（知道堆中的位置）。我认为你需要编写自己的堆代码，并在每次在堆中移动对象时将堆中的索引写入到该对象中。叹。
