java skew heap merging

Question

私はJavaでなければなりませんが、スキューヒープのマージプロセスを理解しようとしています。私は、ステップの太字の部分がそれがなぜそのようになっているのか理解できません。

• 2つのヒープのルーツを比較します。 pを とすると、ルートが小さいほうのヒープになり、q は他のヒープになります。
• 結果の 新しいヒープの名前をrとします。
• rのルートをp （より小さいルート）のルートとし、のrの右 サブツリーをpの左のサブツリーとする。
• ここで、rの左サブツリーを で計算し、pの右サブツリー をqと再帰的にマージします。

は、アルゴリズムを対称軸に沿って変更された（例えば、私は木の鏡面反射を行う）とrの左部分木は、pの右部分木なると、再帰的にRの右側を下にマージしてみましょうことができますか？それは単なる大会ですか、それとも上記のように効率的ですか？

Answer 1

左/右の選択は完全に任意ですが、いったんそれをしたら、それに固執する必要があります。結局のところ、あなたはヒープを取って、その写真を描いて、それを鏡に映しても、それはまだ有効なヒープになるでしょう。これの根底にある理由は、任意のプログラムを取ることができ、変数のすべての出現を左右に入れ替えることができ、結果のプログラムは依然として有効であり、まったく同じことです。