Thread: Implementing a priority queue using a max heap

Hi, I've been working on implementing a priority queue using a max heap and have managed to create a max heap that works however when I try to implement it with the priority queue it doesn't work. I'm not sure if I'm implementing right. Right now I have the two classes in two seperate files.

public class MyMaxHeap{
 
  private Object[] theHeap;
  private int size;
 
  public MyMaxHeap(){
    size=0;
    theHeap = new Object[0];
  }
 
  public MyMaxHeap(int cap)
  {
    size=0;
    theHeap = new Object[cap];
  }
 
  public MyMaxHeap(Object[] arr, int n)
  {
    theHeap=arr;
    size=n;
    buildHeap();
  }
 
  public int getSize()
  {
    return size;
  }
 
  public boolean add(Object o)
  {
    int index;
    if((size>=theHeap.length)||(o==null))
    {
      return false;
    }    
    theHeap[size++]=o;
    index=shiftUp(size-1);
    return true;
  }
 
  public Object removeMax()
  {
    if(size <= 0)
    {
      return null;
    }
    swap(0,--size);
    shiftDown(0);
    return theHeap[size];
  }
 
  private void shiftDown(int index)
  {
    int lc;
    if((index>=0)&&(index<(size/2)))
    {
      lc=2*index+1;
      if(((lc+1)<size)&&((Comparable)theHeap[lc]).compareTo(theHeap[lc+1])<0)
      {
        lc++;
      }
      if(((Comparable)theHeap[index]).compareTo(theHeap[lc])<0)
      {
        swap(index,lc);
        shiftDown(lc);
      }
    }
  }
 
  private int shiftUp(int index)
  {
    int p;
    if((index>0)&&(index<size)){
      p=(index-1)/2;
        if(((Comparable)theHeap[index]).compareTo(theHeap[p])>0){
         swap(p,index);
         return shiftUp(p);
      }
    }
    return index;
  }
 
  private void swap(int x, int y)
  {
    if((x>=0)||(y>=0)||(x<theHeap.length)||(y<theHeap.length)){
    Object temp = theHeap[x];
    theHeap[x]=theHeap[y];
    theHeap[y]=temp;
    }
   }
 
  private void buildHeap()
  {
    int i;
    for(i=(size/2-1);i>=0;i--)
    {
      shiftDown(i);
    }
  }
 
  public void parse()
  {
    int i;
    if(size>0){
    String ret= " ";
    for(i=0;i<size;i++){
      ret+= theHeap[i].toString() + " ";
      System.out.println(ret);
    }
    }
  }
 
 
 
 
public static void main(String[] args){
 
MyMaxHeap heap = new MyMaxHeap(10);
 heap.add(null);
 heap.add(47);
 heap.add(48);
 heap.add(49);
 heap.add(105);
 heap.add(77);
 heap.add(100);
 heap.add(10000);
 heap.add(50);
 heap.add(-10);
 heap.add(-5000);
 heap.add(null);
 heap.add(400);
 heap.removeMax();
 heap.removeMax();
 heap.removeMax();
 heap.removeMax();
 heap.parse();
 
 
 System.out.println(heap.getSize());
}
}

public class MyPriorityQueue extends MyMaxHeap{
 
    private MyMaxHeap theQueue = new MyMaxHeap();
    private Object[] Q;
 
    public MyPriorityQueue(){
 
      theQueue = new MyMaxHeap();
 
    } 
 
public MyPriorityQueue(Object arr[], int n){
 
     theQueue= new MyMaxHeap(arr,n);      
  }
 
 
   public boolean enqueue(Object o){
     if((o==null)||(getSize()<0)){
       return false;
     }
     System.out.println("j");
     System.out.println(theQueue.add(o));
     return theQueue.add(o);
 
    }
 
   public Object dequeue(){
 
     if(theQueue==null){
       return null;
     }
     theQueue.removeMax();
     System.out.println(theQueue.removeMax());
     return theQueue.removeMax();
  }
 
   public Object peek(){
 
     if(theQueue==null){
       return null;
     }
     return theQueue.removeMax();
   }
 
   public static void main(String[] args){
 
 
 
 
 
   }
}

I don't see the point of having a MyPriorityQueue class if you already have a heap class, and I would especially caution against putting a MyMaxHeap as a field of a priority queue which extends MyMaxHeap.

A priority queue is simply a method of traversal where the item with the highest priority (aka value) gets pulled. So if you're max heap class works correctly, all you need to do is pull the root item and you have the highest priority item on the priority queue.

MyMaxHeap priorityQueue = new MyMaxHeap(); // no need for a separate class at all, a Priority queue was implemented directly in MyMaxHeap

A few other things which look concerning:
1. You have an object array as the underlying storage container for your heap class. In general objects are not comparable, especially between different objects (how do you compare a String to a JButton or an ArrayList?). I would strongly recommend creating a heap node class which would contain the data, as well as the "value" of that item on the heap.

public class HeapNode
{
    public Object data; // kind of bad practice, but oh well
    public int value; // use this value in your heap logic, your heap logic shouldn't do any comparisons/checks on data, only on value.
}

Your underlying heap data would then be an array of HeapNodes.