Leftist Heap doesn't support DecreaseKey operation?

Question

I'm studying data structure. When I read the chapter of heap, something really confused me. DecreaseKey's time complexity of the binary heap is O(lgn). However, I found somewhere on internet claimed that Leftist Heap doesn't support DecreaseKey operation. But I wonder why? Can't we simply treat leftist heap as binary heap to perform DecreaseKey?

Answer 1

Indeed, the right solution of DecreaseKey for leftist trees seems to be hidden on the internet. (My book by Weiss has a solution, but in the chapter on amortized analysis, and I do not quickly understand the argumentation.)

First, we cannot treat DecreaseKey as in binary heaps. There one repeatedly swaps the node with its parent until a parent is found which is actually smaller than the new value. This operation works in leftist trees, but may take linear time. In leftist trees there is no bound on the length of paths to the left, and indeed such a tree can be just one long linear leftmost tree.

The solution is to cut the node $q$ that is decreased (with its subtree), to change the value of $q$ to the new value, and merge it with the remainder $T$ of the original tree. Before we can do that we should bring $T$ back into leftist form, and restore the null-path-length values that are changed by cutting the subtree. As we cut $q$ from the tree, only the nodes from the parent $p$ upwards to the root have to be checked. (Unfortunately this may be a linear number of nodes, as we have seen.)

The solution is that the new null-path-length values we asign upwards in the tree are always one larger than the value at the previous level. This process stops when we are in a left child which has new value $\ell$ and its right sibling has value $r$ with $\ell \ge r$. Then the parent already had value $r+1 = \min\{\ell,r\}+1$ and we are done.

We know (from the basic property that makes leftist trees efficient) that a null-path-length value of $\ell$ means that there are $2^\ell-1$ nodes in that subtree, making the operation logarithmic.

The fact that the values upwards in the new tree are always one larger is essential here, that was not (necessarily) true along the path in the original tree.