in this casea -heap can be advantageous in much the same way as -trees finallythere is evidence suggesting that -heaps may outperform binary heaps in practice the most glaring weakness of the heap implementationaside from the inability to perform findsis that combining two heaps into one is hard operation this extra operation is known as merge there are quite few ways to implement heaps so that the running time of merge is (log nwe will now discuss three data structuresof various complexitythat support the merge operation efficiently we will defer any complicated analysis until leftist heaps it seems difficult to design data structure that efficiently supports merging (that isprocesses merge in (ntimeand uses only an arrayas in binary heap the reason for this is that merging would seem to require copying one array into anotherwhich would take (ntime for equal-sized heaps for this reasonall the advanced data structures that support efficient merging require the use of linked data structure in practicewe can expect that this will make all the other operations slower like binary heapa leftist heap has both structural property and an ordering property indeeda leftist heaplike virtually all heaps usedhas the same heap-order property we have already seen furthermorea leftist heap is also binary tree the only difference between leftist heap and binary heap is that leftist heaps are not perfectly balancedbut actually attempt to be very unbalanced leftist heap property we define the null path lengthnpl( )of any node to be the length of the shortest path from to node without two children thusthe npl of node with zero or one child is while npl(nullptr- in the tree in figure the null path lengths are indicated inside the tree nodes notice that the null path length of any node is more than the minimum of the null path lengths of its children this applies to nodes with less than two children because the null path length of nullptr is - the leftist heap property is that for every node in the heapthe null path length of the left child is at least as large as that of the right child this property is satisfied by only one of the trees in figure namelythe tree on the left this property actually goes out of its way to ensure that the tree is unbalancedbecause it clearly biases the tree to get deep toward the left indeeda tree consisting of long path of left nodes is possible (and actually preferable to facilitate merging)--hence the name leftist heap because leftist heaps tend to have deep left pathsit follows that the right path ought to be short indeedthe right path down leftist heap is as short as any in the heap otherwisethere would be path that goes through some node and takes the left child then would violate the leftist property theorem leftist tree with nodes on the right path must have at least nodes