STLヒープをO（logn）時間で実行する減少キー

Question

STLヒープは減少キーをサポートしていませんが、ベクトルの値を直接変更するだけで、O（n）時間のmake_heapを再度呼び出すことができます。しかし、これはO（logn）時間がかかるバイナリヒープ減少キーほど効率的ではありません。

STLヒープ関数を使用してO（logn）時間を達成する方法はありますか？

Answer 1

あなたはpush_heapに続く値をデクリメント続いpop_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()); 
} 

EDIT：これはあなたが何を意味するかですか、でどの要素のキーを減少させることができるようにしたいんヒープ？

Answer 2

私はそれを行うための標準的な準拠の方法はありませんかなり確信している - Wikipedia says so tooは：

それが行くんが減少/増加、キー操作のための標準サポート

はありませんgheapライブラリを指し示すようにしてください。これは一見価値があるかもしれません。

ここでの問題は、標準ではヒープ構造がどのような形式をとるのか、どのように操作が正確に行われるのかを規定していないことです。

実装で標準のバイナリヒープを使用している場合は、要素を単にheap[i]に減らしてから、push_heap(heap.begin(), heap.begin() + i + 1)を呼び出すと、必要なアップヒープ操作が実行されます。位置iに終わる要素は、もともとの値より大きくなくてはならないため、ヒープ全体のヒーププロパティが保持されます。しかし、いくつかの実装では時々動作するとしても、これは標準によってサポートされていません。