[高级数据结构] Week 3 Note 2

Leftist Heaps and Skew Heaps

空路径 NPL：Npl(X) = min { Npl(C) + 1 for all C as children of X }

• 对于堆中的每个节点X，左子节点的空路径长度至少与右子节点的空路径长度相同。

A leftist tree with r nodes on the right path must have at least 2r – 1 nodes.

struct TreeNode 
{ 
  ElementType	    Element;
  PriorityQueue	    Left;
  PriorityQueue	    Right;
  int		    Npl;
} ;