Java

Question

对于编程任务，我一直致力于创建一个程序，该程序读取输入文件并使用 self-made 最大堆优先级队列对内部数据进行排序。数据文件包含读取 "insert [a name] [a number]" 或 "remove" 的行。对于这个优先级队列，我们需要做一个函数来插入和移除objects。队列中的每个 object 都包含字符串形式的名称和整数形式的优先级。我必须基于一个大小为 255 的数组来实现这个堆。

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

1) insert(name, priority): 这个函数应该接受一个字符串类型的名称和一个整数类型的优先级，并将它们插入到优先级队列中。 remove()：此函数应从 object.

中删除具有最高优先级值的 object 和 return 名称字符串

2) 作为背景，我为这个程序准备了三个 classes：首先，"main" class 包含读取文件和使用函数的实现。其次，"name" class，它创建包含名称字符串和优先级 int 的名称 object、构造函数和用于比较两个 object 的优先级值的 compareTo 方法秒。第三，"priorityqueue" class，包含插入和删除功能。现在，这是我为这两个函数编写的伪代码：

插入：

检查数组是否已满（当num = 255时），如果为真则抛出
使用名称字符串和优先级 int
在 num
使用 while 循环在插入时交换两个 objects
更新 num (num++)

删除：

保存第一个object
将最后一个object移到第一个
更新 num (num--)
使用while循环来确定较大的child和return。

3) 这是我目前的代码。我会提供我的名字和优先队列 classes，以防我的名字 class 给我带来麻烦。

优先队列class:

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;
}

}

姓名class:

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) 将始终 return 2*idx+2，除非 idx 为负数。而且，您甚至还没有初始化 idx。你想要的是：

idx = 0;
while (idx < num)

现在，您要做的是查看 names[idx] 是否小于其任一 children。并且，如果是这样，select 两个 children 中最大的一个可以与之交换。所以：

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 设为 method-scoped 变量。它不需要是全局的，并且使其成为方法的局部变量会强制您在使用它之前对其进行初始化，而不是可能（如在现有代码中）使用陈旧的值。

我认为您需要更改 Name class 的 CompareTo 功能。 Comparable compareTo 函数必须 return:

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;
}

Java - 如何在 heap-based 优先级队列中实现函数

Java - How to implement functions in a heap-based priority queue

heap

priority-queue