私は技術面の面接に向けて勉強していて、1、2 年前のデータ構造に関する講義のスライドを読んでいました。
左派ヒープのマージの最悪のケースの実行時間が O(log n) であるのに対し、スキュー ヒープの場合は O(n) である理由が明確ではありません。
左派のヒープは、小さい方のルートを持つツリーを選択し、その右側のサブツリーを大きい方のツリーと再帰的にマージすることで、A と B をマージします。次に、ヌル パスの長さをチェックし、左派の構造プロパティに違反している場合は、2 つのサブツリーを交換します。
スキュー ヒープも同じことを行いますが、A と B を再帰的にマージするたびに 2 つのサブツリーをやみくもに交換します。
スキュー ヒープのマージの最悪のケースが O(n) になるのはなぜですか? 再帰的にマージするときに高さの境界を保証できないためですか (毎回サイドを交換しているため)? これは、ツリー内のすべてのノードの高さの合計が O(n) になるというフロイドのアルゴリズムと関係がありますか?