CODEWITHSUNDEEP
javapriority-queue
M0rty
M0rty

Reputation: 1085

Trouble implementing priority queue Java

I currently have an issue with my priority queue. When i'm testing my methods the I get an error saying my Queue isn't returning the highest priority. I have stepped through and I can't see why the Poll or Offer method is causing this issue. Any help would be appreciated. Thanks

public class HeapArrayQueue <E extends Comparable<? super E> > extends AbstractQueue <E> { 

@SuppressWarnings("unchecked") 
private E[] data = (E[])(new Comparable[7]);
private int count = 0;
private int front = 0;
public int size() {
    return count;
}

public boolean isEmpty() { 
    return size() == 0; 
}

public E poll() {
     if (isEmpty())
        return null;
    else {
        E ans = data[front ];
        front = (front+1);       
        return ans;
    }
}


public boolean offer(E element) {
    if (element == null)return false;
    else {
        ensureCapacity();
        data[count] = element;
        bubbleUpFromIndex(count);
        count++;
        return true;
    }
}

private void bubbleUpFromIndex(int nodeIndex) {
     if (nodeIndex != 0){
         int parent = (nodeIndex -1) / 2;
         if (data[nodeIndex].compareTo(data[parent]) > 0){
             swap(nodeIndex, parent);
             bubbleUpFromIndex(parent);
         }
    }
}

private void swap(int from, int to) {
    E temp = data[from];
    data[from] = data[to];
    data[to] = temp;
}

private void ensureCapacity() {
    if (count == data.length) {
        @SuppressWarnings("unchecked") 
        E[] newData = (E[])new Comparable[data.length * 2];

        for (int loop = 0; loop < count; loop++) {
            newData[loop] = data[loop];
        }
        data = newData;
    }
    return;
}

public Iterator<E> iterator() { 
    return null; 
}
}

Failing test

@Test
public void QueueRespectsPriority() {
    nonEmptyQueue.offer(t1);
    assertEquals("Queue should return element with highest priority", t1, nonEmptyQueue.poll());
}

Upvotes: 0

Views: 343

Answers (2)

Fellow103Student
Fellow103Student

Reputation: 1

In your bubbleUpFromIndex method, your greater-than symbol > needs to be a less-than symbol <. And you should use the poll method in the other answer, then it will work.

Upvotes: 0

FractalMycelium
FractalMycelium

Reputation: 11

Doing comp103 at vic I take it? looks very similar to what I'm doing at the moment.

The first thing I can see is that you're not preserving the correct priority in poll. Here (in pseudocode is my method)

public E poll(){
if (count = 0) return null
E item = root   // We are returning the root node so store it as a var
root = end      // place the end item in root position
end = null      // set end item to null
count--         // subtract count
sinkDown(0)     // Call sink down to restore ordering
return item     // return item
}

Upvotes: 1

Related Questions