Correct heap implementation in a priority queue

Question

My issue is more semantic than functional, As the code does seem to implement the deQueue and enQueue functions correctly.

The reheapDown and reheapUp functions are being used incorrectly, And i believe the issue lies in my heap function

package priqueue;

public class Hosheap{
  private Patient[] elements;
  private int numElements;

  public Hosheap(int maxSize)
  {
    elements= new Patient[maxSize];
    numElements=maxSize;
  }

  public void ReheapDown(int root,int bottom)
  {
    int maxChild;
    int rightChild;
    int leftChild;
    leftChild=root*2+1;
    rightChild=root*2+2;

    if (leftChild<=bottom)
    {
      if(leftChild==bottom)
        maxChild=leftChild;
      else
      {
        if(elements[leftChild].getPriority() <= elements[rightChild].getPriority())
          maxChild=rightChild;
        else
          maxChild=leftChild;
      }
      if(elements[root].getPriority()<elements[maxChild].getPriority())
      {
        Swap(root,maxChild);
        ReheapDown(maxChild,bottom);
      }
    }
  }

  public void ReheapUp(int root,int bottom)
  {
    int parent;
    if(bottom>root)
    {
      parent=(bottom-1)/2;
      if(elements[parent].getPriority()<elements[bottom].getPriority())
      {
        Swap(parent,bottom);
        ReheapUp(root,parent);
      }
    }
  }

 public void Swap(int Pos1, int Pos2)
 {
   Patient temp;
   temp = elements[Pos1];
   elements[Pos1]=elements[Pos2];
   elements[Pos2]=temp;
 }

 public Patient getElement(int e)
 {
   return elements[e];
 }

 public void setElement(Patient p, int n)
 {
    elements[n]=p;
 }
}

The idea is to rearrange a simple priority queue system so when a patient object is removed, ReheapUp or down correctly rearranges the queue, Which the code does not accomplish. Should i also include the priority queue code, Or is this already too lengthy?

I am using NetBeans IDE 6.0.1, If that helps.

Answer 1

Not exactly answering your question, but with Java you may want to look into the built-in Collection classes. You can get priority queue behavior but using a TreeSet (a type of ordered-set) and implementing a custom Comparator for Patient instances. Depending what you're trying to achieve, this may be preferable. It would look something like this:

In Patient.java ...

class Patient implements Comparator { 
...
public int compareTo(Patient other) {
    return getPriority() > other.getPriority() ? 1 : 0;
}

Then in the place you want to use the queue

Set<Patient> queue = new TreeSet<Patient>();
queue.add(p1);
queue.add(p2);
//traverse in order of priority
for(Patient p : queue) {
  doStuff();
}

Answer 2

Depending on your usage requirements, the answer relating to TreeSets will most probably do what you want.

However if you really need a queue, as opposed to a sorted collection, then the inbuilt PriorityQueue may be of use.