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).