オブジェクトの代わりにObject[]配列を使用して実装できるプライオリティ キューのヒープ構造を探しています。Node
もちろん、バイナリ ヒープはうまく機能し、n-ary ヒープも同様です。Javajava.util.PriorityQueueはバイナリ ヒープであり、Object[]配列をストレージとして使用します。
たとえばフィボナッチヒープなど、他にもたくさんのヒープがありますが、私が知る限り、これらはノードを使用して実装する必要があります。そして私のベンチマークから、これらすべてのノード オブジェクトを管理することによって支払われるオーバーヘッドは、得られるすべてのメリットを食いつぶす可能性があるという印象を受けます。単純な配列ベースのバイナリ ヒープと共存できるヒープを実装するのは非常に難しいと思います。
そのため、現在、オブジェクトを使用するオーバーヘッドがない高度なヒープ/優先キュー構造を探していNodeます。複雑な理論だけでなく、実際には高速である必要があるため...実際にはもっと多くのことが起こっています.たとえば、CPUにはパフォーマンスに影響を与えるL1、L2、L3キャッシュなどがあります。
私の質問はJavaにも焦点を当てています。これは、ここではメモリ管理にほとんど影響を与えずstruct、C のように s がないという理由からです。C で実装するとうまく機能するヒープの多くは、Java ではメモリ管理のオーバーヘッドのためにコストがかかります。そしてゴミ収集費用。