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

Question

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

Все дерево нуждается два свойства, которые будут поддерживаться:

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

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

Но какова цель 2-го имущества? Почему мы должны держать правильные короче левого?

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

Answer 1

В статье вы цитируется сказал:

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

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

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

Гарантирует второй.

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