c# - Priority Queue remove items with same priority first one entered

Question

I've got a priority queue created and working that enters items in order and removes them in order. Even if two numbers have the same priority, it removes the one that was entered first.

If there are three numbers that have the same priority, it does not remove the first one. How would I go about doing this, or should it do this?

Dequeue function:

public void deQueue(Animal item)
{
    item = items.elements[0];
    items.elements[0] = items.elements[numItems - 1];
    numItems--;
    items.ReheapDown(0, numItems - 1);
}

ReheapDown Function:

public void ReheapDown(int root, int bottom)
{
    int maxchild, rightchild, leftchild;
    leftchild = root * 2 + 1;
    rightchild = root * 2 + 2;

    if (leftchild <= bottom)
    {
        if (leftchild == bottom)
            maxchild = leftchild;
        else
        {
            if (elements[leftchild].priority <= elements[rightchild].priority)
                maxchild = rightchild;
            else
                maxchild = leftchild;
        }

        if (elements[root].priority < elements[maxchild].priority)
        {
            Swap(elements, root, maxchild);
            ReheapDown(maxchild, bottom);
        }
    }
}

Answer 1

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.