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?
2
-
$\begingroup$ Assuming you have a reference to the node for decreaseKey, you should be able to do an arbitrary remove in then an insert in $O(\log n)$. Check these slides by Sartaj Sahni. $\endgroup$– ryanJun 21, 2017 at 3:31
-
$\begingroup$ Every source I read mentions this "assuming you have a pointer to the node" caveat. What if you don't? Does it mean you have to traverse the entire structure to find that node before it can be decreased/removed? That would be a pretty big limitation with leftist trees. $\endgroup$– DestyDec 15, 2021 at 10:10
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
answered Nov 11, 2018 at 16:20
-
$\begingroup$ Now can someone please change the summary of running times for decrease-key for leftist trees on the Wikipedia page for the priority queue (which lists O(n) complexity)?? $\endgroup$ Nov 11, 2018 at 16:20