Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
392 views
in Technique[技术] by (71.8m points)

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

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);
        }
    }
}
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...