Leftist heap
= Leftist heap
A binary <meldable heap> satisfying <heap order> and the leftist condition: at each node, the shortest path to a missing child is no longer in the right subtree than in the left. Melding recurses down right spines, swaps children when needed, and takes logarithmic time.