Trouble implementing priority queue Java

Question

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

t1 is an object that implements comparable. I don't believe it overrides the equals method — M0rty
– M0rty, Commented Oct 16, 2014 at 7:25
For assertEquals to work with custom objects, the equals method should be overridden. — JamesB
– JamesB, Commented Oct 16, 2014 at 7:30
So you don't believe there is anything wrong with my queue methods? — M0rty
– M0rty, Commented Oct 16, 2014 at 7:32
Possibly not. Override equals and hashCode methods for type t1 and try again. — JamesB
– JamesB, Commented Oct 16, 2014 at 7:33

FractalMycelium · Accepted Answer · 2014-10-18 08:33:12Z

1

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
}

answered Oct 18, 2014 at 8:33

FractalMycelium

111 bronze badge

Sign up to request clarification or add additional context in comments.

Comments

Unihedron · Accepted Answer · 2014-10-18 10:45:12Z

0

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.

edited Oct 18, 2014 at 10:45

Unihedron

11.1k13 gold badges65 silver badges72 bronze badges

answered Oct 18, 2014 at 10:41

Fellow103Student

1

Collectives™ on Stack Overflow

Trouble implementing priority queue Java

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related