Какова реальная цель звания в левой куче?

Question

Левая куча поддерживает ключ и ранг для каждого узла. Ранг узла - это количество узлов вдоль кратчайшего пути к листу.

Целому дереву необходимо поддерживать два свойства:

1. node.key
2. node.left.rank> = node.right.rank

Я могу понять первое свойство, так как это куча, и это естественно.

Но какова цель второго свойства? Почему нужно держать правую короче левой?

Для балансировки?

Answer 1

В цитируемой вами статье сказано:

Эти условия гарантируют, что левое дерево является кучей (элемент с минимальным ключом находится на вершине кучи) и что кратчайший путь к конечному узлу получается путем перехода по правой ссылке

Состояние, о котором вы спрашивали, и

P.rank = 1 + min( (P.left).rank, (P.right).rank );

Обеспечивает второе.

Поскольку операция объединения выполняется вдоль правых узлов, это обеспечивает логарифмическую производительность объединения.