I’m sorry but my English is kinda rusty, so I don’t fully understand your question.
Anyway, I show an example of what pairing heaps do in the simplest way, without custom comparator, so the smallest items should appear at the top.
An empty pairing heap is just nil.
Push 1
{1, []}
Then push 2
{1, [
{2, []}
]}
Then push 3
{1, [
{3, []},
{2, []}
]}
Note that 3 appears before 2, because adding items to the head of a list is cheaper than adding items to the end.
Then push 4 then 5 then 6
{1, [
{6, []},
{5, []},
{4, []},
{3, []},
{2, []}
]}
When pushing items greater than the root into a non-empty pairing heap, the newly added items always appear at the second-top layer.
Then push 0
{0, [
{1, [
{6, []},
{5, []},
{4, []},
{3, []},
{2, []}
]}
]}
Pushing an item smaller than the root, the newly added item becomes the new root, and the existing heap becomes its child.
What happens when pushing an item equal to the root?
Well, you can make it the new root, you can also make it the new child of the existing root. It depends on how you implement the pairing heap. Pairing heap does not ensure FIFO of the equal items.
Let’s do a pop
Obviously we should remove 0. Since it has only one child, we are done.
{1, [
{6, []},
{5, []},
{4, []},
{3, []},
{2, []}
]}
Pop again
This time, we should pop the root 1 out of the heap, but just removing 1 makes the heap no longer a tree. So we have to elect a new root. Here comes the pairing procedure.
We take the second layer, and make them 3 pairs.
# Pair1
{
{6, []},
{5, []}
}
# Pair 2
{
{4, []},
{3, []}
}
# Pair 3
{
{2, []},
nil
}
Note that {2, []} has no other child to pair with, so we pair it with nil.
Which child pairs with which child is kinda arbitrary, as long as a child only gets paired once. I just use the easiest way.
Then, for each pair, we build a sub pairing heap. This is called meld. The melding procedure is very simple. Pick the smaller one in the pair to be the root, and add the bigger one to the second layer of the smaller one.
# The heap built with the first pair
{5, [
{6, []}
]}
# The heap built with the second pair
{3, [
{4, []}
]}
# The heap built with the third pair
{2, []}
There are still more than 1 heaps, so we do the pair-and-meld again.
Pairing:
# Pair 1
{
{5, [
{6, []}
]},
{3, [
{4, []}
]}
}
# Pair 2
{
{2, []},
nil
}
Melding:
# Heap built with pair 1
{3, [
{5, [
{6, []}
]},
{4, []}
]}
# Heap built with pair 2
{2, []}
Well, there are still 2 heaps, so we pair them up and meld again. The result is
{2, [
{3, [
{5, [
{6, []}
]},
{4, []}
]}
]}
The idea of pairing heap is to postpone the restructuring until the heap become multiple trees.
