Implementation of priority queue and max heap

[jsinclair1482]

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){





}
}

[dlorde]

Please post code inside CODE tags (see my sig) so it remains readable.

E.T.A. Ah, don't bother - I see you've cross-posted on Java Programming Forums. I'm out.


Programs must be written for people to read, and only incidentally for machines to execute...
H. Abelson and G. Sussman