3

オブジェクトの代わりにObject[]配列を使用して実装できるプライオリティ キューのヒープ構造を探しています。Node

もちろん、バイナリ ヒープはうまく機能し、n-ary ヒープも同様です。Javajava.util.PriorityQueueはバイナリ ヒープであり、Object[]配列をストレージとして使用します。

たとえばフィボナッチヒープなど、他にもたくさんのヒープがありますが、私が知る限り、これらはノードを使用して実装する必要があります。そして私のベンチマークから、これらすべてのノード オブジェクトを管理することによって支払われるオーバーヘッドは、得られるすべてのメリットを食いつぶす可能性があるという印象を受けます。単純な配列ベースのバイナリ ヒープと共存できるヒープを実装するのは非常に難しいと思います。

そのため、現在、オブジェクトを使用するオーバーヘッドがない高度なヒープ/優先キュー構造を探していNodeます。複雑な理論だけでなく、実際には高速である必要があるため...実際にはもっと多くのことが起こっています.たとえば、CPUにはパフォーマンスに影響を与えるL1、L2、L3キャッシュなどがあります。

私の質問はJavaにも焦点を当てています。これは、ここではメモリ管理にほとんど影響を与えずstruct、C のように s がないという理由からです。C で実装するとうまく機能するヒープの多くは、Java ではメモリ管理のオーバーヘッドのためにコストがかかります。そしてゴミ収集費用。

4

1 に答える 1

3

この方法で、いくつかの珍しいヒープ構造を実装できます。たとえば、Dijkstra の Smoothsort アルゴリズムで使用される Leonardo Heapは、通常、2 つの機械語で拡張された配列として実装されます。バイナリ ヒープと同様に、配列表現は特定のツリー構造 (または、ツリーのコレクションであるため、フォレスト) の配列表現です。

poplar ヒープ構造は、理論的には効率がわずかに劣りますが、実際には同じ基本的な考え方を持つヒープ構造として導入されました。データは、いくつかの非常に小さな状態情報を持つ配列として表され、フォレスト構造の圧縮表現です。

より標準的な配列ベースのヒープはd-ary ヒープです。これは、バイナリ ヒープを 2 つではなく d つの子を持つように自然に一般化したものです。

非常にばかげた例として、並べ替えられた配列を優先キューとして使用できますが、非常に非効率的です。

お役に立てれば！

于 2013-01-09T18:34:40.077 に答える