6

ヒープの PHP 実装は本当に完全な実装ですか?

この記事http://en.wikipedia.org/wiki/Heap_%28data_structure%29を読むと、子ノードには特定の親があり、親には特定の子があることがわかります。

ただし、PHP ドキュメントhttp://au.php.net/manual/en/class.splheap.phpの例を見ると、子ノードはすべて同じ「レベル」を共有しているように見えますが、特定の親/子供の情報は重要ではありません。

たとえば、PHP の例で 10 位にランクされている 3 つのノードのそれぞれの親ノードはどれですか?

私のアプリケーションでは、ユーザーが「ノード 156」を選択したときに、その子が誰であるかを知る必要があります。(それらの ID を「ノード 1561」、「ノード 1562」などにすることができるので、関係は明らかです)。

PHP ヒープの実装は不完全ですか? Splクラスを忘れて、自分の道を行くべきですか？または、ヒープの動作方法について何か不足していますか? それとも、特定のヒープ バリアントを確認する必要がありますか?

ありがとうございます！

4

2 に答える 2

8

このヒープ実装の API は配列アクセスを許可していません。これは、この場合に必要なものです。ヒープは通常、上部からアイテムを簡単に削除できる他の構造を実装するために使用されます。

必要な位置をシークするラッパー イテレータを作成できます。これはパフォーマンスの低いソリューションであり、あまり良いソリューションではないのではないかと思います。

この状況では、 aBinaryTreeが必要だと思います。ツリー内のスポットを指定すると、それらは直接リンクされているため、子になります。ツリーの順序を維持するBinarySearchTreegetRootがあり、呼び出してBinaryTree. 最適な検索のためにツリーのバランスを保つAvlTreeもあります。

于 2012-11-29T17:59:24.653 に答える
4

ヒープは通常、「セット内の最大/最小要素は何ですか」を中心とした質問に答えるために使用されます。

ヒープは偶然にも「最大/最小ノードの子は誰ですか」と効率的に答えることができますが、質問に答えるために任意のノードにアクセスする必要がある場合に使用するのに適したデータ構造としては目立ちません。最大ノードではありません）。また、表現および維持する必要のある特定の親子関係がある場合に使用するデータ構造ではありません。これは、子が異なる親ノード間で交換される可能性があり、実際に交換されるためです。

したがって、phpのヒープ実装は、これらの理由で間違いなく不完全ではありません。別のデータ構造が必要なだけです。

于 2012-10-14T22:18:25.583 に答える