Java - 如何在基于堆的优先级队列中实现函数

Question

对于一项编程作业，我一直致力于创建一个程序，该程序读取输入文件并使用自制的最大堆优先级队列对内部数据进行排序。数据文件中的行要么是“插入[名称] [数字]”，要么是“删除”。对于这个优先级队列，我们​​需要制作一个插入和删除对象的函数。队列中的每个对象都包含字符串形式的名称和整数形式的优先级。我必须基于一个大小为 255 的数组来实现这个堆。

我的问题是，我很难实现插入和删除功能以按指定方式工作。我将提供 1) 它们需要如何工作，2) 我制作的伪代码，以及 3) 我实现的实际 Java 代码。我的两个函数都没有完全按照我的预期工作，因此我可以使用更有经验的程序员的一些指导。

1) insert(name,priority):该函数应获取字符串类型的名称和整数类型的优先级，并将它们插入到优先级队列中。 remove():此函数应删除具有最高优先级值的对象并从该对象返回名称字符串。

2)作为背景，我为该程序提供了三个类:首先，“主”类包含用于读取文件和使用函数的实现。其次，“name”类，它创建包含名称字符串和优先级 int 的名称对象、构造函数以及用于比较两个对象的优先级值的compareTo 方法。第三，“priorityqueue”类，包含插入和删除函数。现在，这是我为这两个函数编写的伪代码:

插入:

• 检查数组是否已满(当num = 255时)，如果为true则抛出
• 使用名称字符串和优先级 int 从输入文件创建对象
• 在 num 处插入对象
• 使用 while 循环在插入时交换两个对象
• 更新 num (num++)

删除:

• 保存第一个对象
• 将最后一个对象移动到第一个对象
• 更新 num (num--)
• 使用 while 循环来确定较大的子级并将其返回。

3)这是我到目前为止的代码。我将提供我的名称和优先级队列类，以防我的名称类给我带来麻烦。

优先级队列类别:

public class PriorityQueue 
{
int num; //amount of things in array 
int idx; //index of current name object
Name[] names = new Name[255];

public void insert(String name, int priority)
{
    while (num != 255)
    {
        Name addName = new Name(name, priority);
        names[num] = addName;
        num++;

        while(idx != 0 || names[idx].CompareTo(names[(idx-1)/2]))
        {
            Name temp = names[idx];
            names[idx] = names[(idx-1)/2];
            names[(idx-1)/2] = temp;

            idx = (idx-1)/2;
        }
    }
}

public Name remove()
{
    Name temp2 = names[0];
    //Save first element

    names[0] = names[idx];
    //Move last element to first

    num--;
    while(idx < Math.max(2*idx+1,2*idx+2))
    {
        if(names[idx].CompareTo(names[(idx-1)/2]))
                {
                    Name temp3 = names[idx];
                    names[idx] = names[(idx-1)/2];
                    names[(idx-1)/2] = temp3;
                }
    }
    return temp2;
}

}

命名类:

public class Name implements Comparable
{
String name;
int priority;

public Name(String n, int i)
{
    name = n;
    priority = i;
}

public boolean CompareTo(Name obj)
{
    if(priority < obj.priority)
    {
        return false;
    }

    else if(priority > obj.priority)
    {
        return true;
    }

    return true;
}
}

我很感激任何帮助。谢谢!

Answer 1

几个问题。首先，在您的 insert 方法中:

public void insert(String name, int priority)
{
    while (num != 255)
    {
        Name addName = new Name(name, priority);
        names[num] = addName;
        num++;

        while(idx != 0 || names[idx].CompareTo(names[(idx-1)/2]))
        {
            Name temp = names[idx];
            names[idx] = names[(idx-1)/2];
            names[(idx-1)/2] = temp;

            idx = (idx-1)/2;
        }
    }
}

while (num != 255) 不应该在那里。您应该检查是否num == 255，如果是则抛出异常。

然后，您需要初始化idx。即:

        Name addName = new Name(name, priority);
        names[num] = addName;
        idx = num;
        num++;

并且您的 while 条件应使用 && 而不是 ||。否则每次 idx 不等于 0 时都会进行交换。

在您的remove方法中:

public Name remove()
{
    Name temp2 = names[0];
    //Save first element

    names[0] = names[idx];
    //Move last element to first

    num--;
    while(idx < Math.max(2*idx+1,2*idx+2))
    {
        if(names[idx].CompareTo(names[(idx-1)/2]) > 0)
                {
                    Name temp3 = names[idx];
                    names[idx] = names[(idx-1)/2];
                    names[(idx-1)/2] = temp3;
                }
    }
    return temp2;
}

您不需要 names[idx] 存在，因为您不知道 idx 是什么。你想要:

names[0] = names[num-1]; // get last item in the heap

这里的 while 条件很愚蠢。 Math.max(2*idx+1,2*idx+2) 将始终返回 2*idx+2，除非 idx 为负数。而且，您甚至还没有初始化 idx。你想要的是:

idx = 0;
while (idx < num)

现在，您要做的是查看 names[idx] 是否小于其子级。如果是这样，请选择两个子项中最大的一个来交换它。所以:

while (idx < num)
{
    int largestChild = idx*2+1;
    if (largestChild >= num) break; // idx is at a leaf level
    if (largestChild+1 < num)
    {
        // compare the two children
        if (names[largestChild].compareTo(names[largestChild+1]) < 0)
        {
            largestChild = largestChild+1;
        }
    }
    if (names[idx] < names[largestChild])
    {
        // swap, moving the item down
        temp = names[idx];
        names[idx] = names[largestChild];
        names[largestChild] = temp;
        idx = largestChild;
    }
    else
    {
        // item is in the proper place
        break;
    }
}

我建议在这两种方法中将 idx 设为方法范围的变量。它不需要是全局的，并且使其成为方法的本地变量会迫使您在使用它之前对其进行初始化，而不是潜在地(如在现有代码中)使用过时的值。

我认为您需要更改 Name 类的 CompareTo 函数。 Comparable compareTo 函数必须返回:

a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

所以你应该:

public boolean CompareTo(Name obj)
{
    if(priority < obj.priority)
    {
        return -1;
    }

    if (priority > obj.priority)
    {
        return 1;
    }

    return 0;
}