問題タブ [binary-heap]

Binary Heap プライオリティ キュー ADT に increaseKey() メソッドを実装する必要がありますが、その方法がわかりません。BinaryHeap は、a.compareTo(b) を使用できるようにする Comparable を拡張するオブジェクトを受け入れるだけですが、オブジェクトのキーを増やす明確な方法はありません。

それで、これを行う方法のアイデアはありますか？Google と here で検索しましたが、これまでに見たバイナリヒープの実装では、これらのメソッドが含まれていないか、エラーが返されます。

Boost d_ary_heap を使用しようとしていますが、プッシュされた要素のハンドルを取得する方法がわかりません。私の場合、後の反復で値を更新する必要があるため、そのハンドルが必要です。私はフィボナッチヒープでそれを行うことができましたが、この場合はもっと複雑に見えます.

これは私がこれまでに持っているものです:

プッシュ関数は、handle_type を返すフィボナッチ ヒープで使用する方法です。しかし、この場合、何を返すべきか理解できません( http://www.boost.org/doc/libs/1_55_0/doc/html/boost/heap/d_ary_heap.html#idp52218904-bb )

押すときにハンドルを取得する方法についてのヘルプは大歓迎です! ありがとう。

サイズが 500 万を超えるベクトルがあり、そのたびにベクトルから最小のキーを持つ 1 つの要素を選択し、この要素に対して何らかの処理を行います。ただし、この特定の要素を処理すると、ベクトル内の残りのすべての要素も影響を受け、キーが更新されます。次回、ベクトルから最小のキーを持つ要素を取得したい場合は、ベクトルをもう一度並べ替える必要があります。問題は、ベクトルから最小の要素を取得する回数が 50 万回に達するため、プログラムの実行が非常に遅くなることです。より明確に理解できるように、次のコードを記述して説明します。

コードをできるだけ効率的に実行する方法はありますか? 並列化など、アルゴリズムの限定的な改善ではなく、どんなアイデアでも大歓迎です。どうもありがとう！