左派堆的等級的真正目的是什麼？

Question

Leftist heap爲每個節點維護一個密鑰和一個等級。節點的等級是葉子最短路徑中的節點數量。

整個樹需要維護兩個屬性：

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

我可以理解第一個屬性，因爲它是一堆並且很自然。

但是第二個屬性的目的是什麼？爲什麼我們需要保持右側比左側短？

爲了平衡目的？

Answer 1

你所引用的文章中說：

這些條件保證了左派樹是一個堆（以最小的關鍵元素是在堆的頂部），以及向葉的最短路徑節點是由以下的rightlink

您詢問了病情和

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

確保第二獲得。

因爲融合操作是沿着正確的節點，這確保了融合的對數表現。