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

Question

For a programming assignment, I have been working on creating a program that reads an input file and sorts the data inside using a self-made max heap priority queue. The data file has lines that either read "insert [a name] [a number]", or "remove". For this priority queue, we need to make a function for inserting and removing objects. Each object in the queue contains the name as a string, and the priority as a integer. I have to implement this heap based on an array with a size of 255.

My question is, I'm having difficulty implementing my insert and remove functions to work as specified. I'll provide 1) how they need to work, 2) pseudocode I've made, and 3) the actual Java code I've implemented. Both of my functions do not work exactly as I intend for them to, so I could use some direction from more experienced programmers.

1) insert(name, priority): this function should take a name of type string and a priority of type integer, and inserts them into the priority queue. remove(): this function should remove the object with the highest priority value and return the name string from the object.

2) As background, I have three classes for this program: First, the "main" class containing implementation for reading the file and using the functions. Second, the "name" class, which creates the name object containing the name string and priority int , a constructor, and a compareTo method for comparing the priority values of two objects. Third, the "priorityqueue" class, contains the insert and remove functions. Now, here is the pseudocode I made for those two functions:

insert:

• Check if the array is full (when num = 255), throw if true
• Create the object from the input file with a name string and priority int
• Insert the object at num
• Use a while loop to swap the two objects at insertion
• Update num (num++)

remove:

• Save the first object
• Move the last object to the first
• Update num (num--)
• Use a while loop to determine the larger child and return it.

3) Here is the code I have so far. I'll provide my name and priority queue classes, in case my name class is what's giving me trouble.

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

}

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

I appreciate any help. Thanks!

Answer 1

Several problems. First, in your insert method:

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

The while (num != 255) shouldn't be there. You should check to see if num == 255, and throw an exception if it is.

Then, you need to initialize idx. That is:

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

And your while condition should use && rather than ||. Otherwise you'll do the swap every time idx is not equal to 0.

In your remove method:

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

You don't want names[idx] there, because you don't know what idx is. You want:

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

Your while condition here is goofy. Math.max(2*idx+1,2*idx+2) will always return 2*idx+2, unless idx is negative. And, again, you haven't even initialized idx. What you want here is:

idx = 0;
while (idx < num)

Now, what you're trying to do is see if names[idx] is smaller than either of its children. And, if so, select the largest of the two children to swap it with. So:

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

I would suggest making idx a method-scoped variable in both methods. There's no need for it to be a global, and making it local to the methods forces you to initialize it before you use it, rather than potentially (as in your existing code) using a stale value.

I think you need to change your Name class's CompareTo function. The Comparable compareTo function must return:

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

So you should have:

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

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

    return 0;
}