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

Question

1）insert（name,priority）：这个函数应该取一个string类型的名称和一个integer类型的优先级，并将它们插入到优先级队列中。remove（）：这个函数应该移除具有最高优先级值的对象，并从对象中返回名称字符串。

2）作为背景，我有三个类用于这个程序：第一，包含读取文件和使用函数的实现的“main”类。第二，“name”类，它创建包含名称字符串和优先级int的name对象、一个构造函数和一个用于比较两个对象的优先级值的compareTo方法。第三，“priorityqueue”类，包含insert和remove函数。下面是我为这两个函数制作的伪代码：

插入：

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

删除：

null

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

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[0] = names[num-1]; // get last item in the heap

idx = 0;
while (idx < num)

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函数。可比的compareTo函数必须返回：

负整数、零或正整数，因为此对象小于、等于或大于指定对象。

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

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

    return 0;
}