Полагаю, вы знаете, какой элемент в контейнере кучи (индекс 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), эта функция расширяет диапазон, который считается кучей, до [first, last), помещая значение в (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. Я думаю, вам нужно написать свой собственный код кучи и записать индекс в куче для объекта каждый раз, когда объект перемещается в куче. Вздох.