C# 中的 PriorityQueue 初始化排序不正确

Question

我尝试用 c sharp 实现这个优先级队列。这是我的代码：

public class PriorityQueue<T> where T : IComparable<T>
{
    private List<T> data;

    public PriorityQueue()
    {
        this.data = new List<T>();
    }

    public void Add(T item)
    {
        data.Add(item);
        int child = data.Count - 1;
        while (child > 0)
        {
            int parent = (child + 1) / 2;
            if ((data[child].CompareTo(data[parent])) >= 0)
                break;

            T temp = data[child];
            data[child] = data[parent];
            data[parent] = temp;
            child = parent;
        }
    }

    public T Get()
    {
        int last = data.Count - 1;
        T root = data[0];
        data[0] = data[last];
        data.RemoveAt(last);
        --last;

        int parent = 0;
        while (true)
        {
            int child = (parent * 2) + 1;
            if (child > last)
                break;
            if (child > last)
                break;
            int next = child + 1;
            if (next <= last && data[next].CompareTo(data[child]) < 0)
                child = next;

            if (data[parent].CompareTo(data[child]) <= 0)
                break;

            T temp = data[parent];
            data[parent] = data[child];
            data[child] = temp;
            parent = child;
        }
        return root;
    }

    public int Count()
    {
        return data.Count;
    }
}

然而，在我的最终结果中，优先队列中的每个项目都正确排序，除了第一个项目 I "get"。第一个似乎是完全随机的顺序。其他所有项目似乎都井井有条。不确定我在这里做错了什么。

Answer 1

简单的小错误。在 Add 函数中，'parent' 被错误地初始化。您应该从 'child' 中减去 1，而不是加 1。应该是这样的：

int parent = (child - 1) / 2;

C# 中的 PriorityQueue 初始化排序不正确

PriorityQueue initialization in C# does not sort properly

c#

queue

priority-queue

data-structures