Реализация ключа уменьшения с кучей STL за время O (logn) - PullRequest
Новая
       23

Реализация ключа уменьшения с кучей STL за время O (logn)

9 голосов
/ 24 марта 2012

В настоящий момент STL Heap не поддерживает клавишу уменьшения, однако можно просто изменить значение вектора напрямую и снова вызвать make_heap, что составляет O (n) раз. Однако это не так эффективно, как бинарный ключ уменьшения кучи, который потребует O (logn) времени.

Есть ли способ достичь времени O (logn), используя функции кучи STL?

Ответы [ 2 ]

4 голосов
/ 29 марта 2012

Я почти уверен, что нет никакого стандартного способа сделать это - Википедия тоже так говорит :

нет стандартной поддержки клавиши уменьшения / увеличенияоперация

Несмотря на то, что она продолжает указывать на библиотеку gheap, на которую вполне стоит обратить внимание.

Проблема в том, что стандарт не предписывает какую формуструктура кучи не принимает ни того, как именно выполняются операции.(В общем, это хорошо.)

Если реализация использует стандартную двоичную кучу, тогда я думаю, что вы можете просто уменьшить элемент на heap[i] и затем вызвать push_heap(heap.begin(), heap.begin() + i + 1), что сделает необходимоеоперация поднятия кучи.Элемент, который заканчивается в позиции i, должен быть не больше первоначального значения, поэтому свойство кучи всей кучи сохраняется.Но это не поддерживается стандартом, даже если он иногда работает в некоторых реализациях.

1 голос
/ 24 марта 2012

Вы можете использовать pop_heap с последующим уменьшением значения с последующим push_heap: 

int main() {
    //Create the heap
    std::vector<int> heap{1,2,3,4,5,6,7};
    std::make_heap(heap.begin(), heap.end());

    //Decrease key
    std::pop_heap(heap.begin(), heap.end());
    --*(std::prev(heap.end()));
    std::push_heap(heap.begin(), heap.end());
}

РЕДАКТИРОВАТЬ: Это то, что вы имеете в виду, или вы хотите уменьшить ключ любого элемента в куче?

...