Leftist Heaps

Definition of NPL

The null path length, Npl(X), of any node X is the length of the shortest path from X to a node without two children. Define Npl(NULL) = -1. \(Npl(X)=\min\{Npl(C)+1, \rm for\ all\ C\ as\ children\ of\ X\}\)

Definition of leftist heap

The leftist heap property is that for every node X in the heap, the null path length of the left child is at least as large as that of the right child.

Theorem

A leftlist tree with \(r\) nodes on the right path must have at least \(2^{r} - 1\) nodes.

Insertion(merge)

• Merge(H1->Right, H2)
• Attach(H2, H1->Right)
• Swap(H1->Right, H1->Left) if necessary

DeleteMin

• Delete the root
• Merge the two subtrees

Time Complexity

\(T_p=O(\log{N})\)