In this line
if (elements[leftchild].priority <= elements[rightchild].priority)
you swap elements if they're equal. So let's say you enter the numbers [2, 2, 1, 3]
, in that order. Let's call the second 2
, "2*
", to differentiate it from the first one. The resulting heap is:
1
/
2 2*
/
3
Now, you remove 1
. So then you replace the 1
with 3
:
3
/
2 2*
In your ReheapDown
method, the parent has two children, and you're selecting the smallest child. When you compare the two 2
's, you have this code:
if (elements[leftchild].priority <= elements[rightchild].priority)
maxchild = rightchild;
else
maxchild = leftchild;
Since 2 == 2
, it sets maxchild = rightchild
, so the new root becomes 2*
--the second 2
that was entered. Your heap now looks like this:
2*
/
2 3
And the next thing to be removed will be 2*
.
You might think, then, that if you change that <=
to <
, it'll solve your problem. But it won't.
When you consider all the different ways that the heap can mutate, it's impossible to guarantee that equal items will be removed in the same order that they were inserted, unless you supply additional information. Consider what happens if you enter items in the order [1, 3, 2, 2*]
. The resulting heap is:
1
/
2* 2
/
3
If you remove 1
, you end up with:
3
/
2* 2
In this case, the <=
would help you out. But in the previous case, it wouldn't.
The only way to guarantee removal order of equal items is to add a second condition on your comparison--basically, you have to make those equal items unequal. You either need to add a date stamp or sequential number to the key so that you can identify the insertion order.