問題タブ [heap]

最初にヒューリスティックに基づいて要素の優先度を決定する優先度キューを使用しています。要素がデキューされると、ヒューリスティックが更新され、現在キューにある要素のキーが増加する場合があります。

O(1) キーの減少操作を償却したヒープ (具体的にはフィボナッチ ヒープ) があることは知っていますが、キーの増加操作に同様の境界を持つヒープ構造はありますか?

私のアプリケーションでは、これはパフォーマンスの問題ではありません (バイナリ ヒープは正常に動作します)。これは、単に学術的な好奇心の問題です。

編集：明確にするために、キーを減らすのではなく、キーを増やす操作の時間が O(logn) よりも速いデータ構造を探しています。私のアプリケーションは、ヒューリスティックが優先度を過大評価するため、キーを減らすことはありません。

私はここphpでヒープソートに固執しています：

配列を並べ替えることができません。何が問題なのかわかりませんか？

やや怠惰に実装したプログラムに興味深いバグを見つけ、それを正しく理解しているかどうか疑問に思いました。短いバージョンでは、Pythonのheapq実装は実際にはリストを並べ替えず、ヒープ中心の方法でリストを作成するだけです。具体的にはheapify()、順序付けられた方法でリストの理解を容易にする順序付けられたリストになることを期待していました。

Pythonのドキュメントのように、優先度キューの例を使用します。

結果は

これは、リストの元の順序ではなく、ここで説明するヒープ中心の順序であることに注意してください。私はこれが完全に注文されることを怠惰に期待していました。

テストとして、heapify（）を介してリストを実行しても、変更はありません（リストはすでにヒープのように順序付けられているため）。

関数を使用してリストを反復処理すると、heappop()期待どおりの順序になります。

したがって、heapq（少なくとも人間の意味では）リストを順序付けないように見えますが、heappush()andheappop()関数はヒープのように順序付けられたリストを取得できます。

結果：ヒープリストに対するスライスおよびリスト内包演算は、順序付けされていない結果になります。

これは本当ですか、そしてこれは常に本当ですか？

（BTW：WinXPシステム上のPython 3.0.1）

SQL Server 2008 を使用しています。テーブルにクラスター化インデックスがない場合はヒープと呼ばれ、それ以外の場合はストレージ モデルがクラスター化インデックス (B ツリー) と呼ばれます。

ヒープ ストレージの正確な意味、外観、「ヒープ」データ構造 (最小ヒープ、最大ヒープなど) として編成されているかどうかについて詳しく知りたいです。おすすめの読み物は？もう少し内部構造を知りたいのですが、深すぎません。:-)

前もって感謝します、ジョージ

私はJavaでのフィボナッチヒープの実装に約1週間取り組んできました。これは、CLRSブックに基づいた実装です。

JavaのデフォルトのPriorityQueueと比較して、作業中のサイドプロジェクトでそれを使用してパフォーマンスが向上するかどうかを確認したかったのです。[Javaのデフォルトの実装は配列ベースであるため、はるかにローカルです。複雑さの限界が高いにもかかわらず、それでもFヒープを上回る可能性があります]。

私の問題は、min要素を削除した後のヒープの統合部分に起因しているようです。arrayindexoutofboundsexceptionsがスローされ続けます。特にwhileループでは、同じ次数を持つすべてのノードを統合します。D（）関数で設定された範囲を超えています。

したがって、私のD（）関数が間違っているか、そうではないと思います。または、何か他のことが起こっています。最も可能性の高い副作用関連。

コードはここにあります。私はこれを約1週間デバッグしようとしてきましたが、運が良かったです。明らかな何かが欠けていますか？

ヒープの抽出分を実装する必要があります (可能であれば C++ で)、STL ヒープからこのメソッドを取得できませんでした。

O(log n) でキーの減少機能を実現できることは知っていますが、方法がわかりません。

配列として格納されている 2 つの最大ヒープをマージするための効率的なアルゴリズムはありますか?

C スタイル言語でランタイム ヒープが動的メモリ割り当てに使用され、データ構造が両方とも「ヒープ」と呼ばれるのはなぜですか? 何か関係あるの？

heapq libsによって作成されたPythonヒープを覗く公式の方法は何ですか？今私は持っています

これは間違いなく、あまり良くありません。heap[0]それがヒープの一番上であると常に想定して使用できますか？それとも、基礎となる実装が多すぎると想定しますか？