Why does pairing heap need that special two passes when delete_min?

Question

I am reading the Pairing heap.

It is quite simple, the only tricky part is the delete_min operation.

The only non-trivial fundamental operation is the deletion of the minimum element from the heap. The standard strategy first merges the subheaps in pairs (this is the step that gave this datastructure its name) from left to right and then merges the resulting list of heaps from right to left:

I don't think I need copy/paste the code here, as it is in the wiki link.

My questions are

1. why they do this two pass merging?

2. Why they first merge pairs? not directly merge them all?

3. also why after merging pairs, merge specifically from right to left?

Answer 1

With pairing heap, adding an item to the heap is an O(1) operation because all it does is add the node either as the new root (if it's smaller than the current root), or as the first child of the current root. So if you created a pairing heap and added the numbers 0 through 9 to it, in order, you would end up with:

        0
        |
-----------------
| | | | | | | | |
9 8 7 6 5 4 3 2 1

If you then do a delete-min, you then have to look at each child to determine the minimum item and build the new heap. If you use the naive left to right combining method, you end up with this tree:

       1
       |
---------------
| | | | | | | |
9 8 7 6 5 4 3 2

And the next time you do a delete-min you have to look at the 8 remaining children, etc. Using this technique, creating and then removing all items from the heap would be an O(n^2) operation.

The two-pass method of combining in pairs and then combining the pairs results in a much more efficient structure. Consider the first case. After deleting the minimum item, we're left with the nine children. They're combined in pairs from left to right to produce:

  8  6  4  2  1
 /  /  /  /
9  7  5  3

Then we combine the the pairs right to left. In steps:

  8  6  4    1
 /  /  /    /
9  7  5    2
          /
         3

  8  6    1
 /  /    / \
9  7    2   4
       /   / 
      3   5  

  8     1
 /      |
9   ---------
    6   4   2
   /   /   /
  7   5   3

      1
      |
  ----------
  8  6  4  2
 /  /  /  /
9  7  5  3

Now, the next time we call delete-min, there are only four nodes to check, and the next time after that there will only be two. Using the two-pass combining method reduces the number of nodes at the child level by at least half. The arrangement I showed is the worst case. If the items were in ascending order, the first delete-min operation would result in a tree with only two child nodes below the root.

This is a particularly good example of the amortized complexity of pairing heap. insert is O(1), but the first delete-min after a bunch of insert operations is O(n), where n is the number of items that were inserted since the last delete-min. The beauty of the two-pass combining rule is that it quickly reorganizes the heap to reduce that O(n) complexity.

With this combining rule, the amortized complexity of delete-min is O(log n). With the strict left-to-right rule, it's O(n).