LinkBack URL
About LinkBacks
Priority Queue in Java which keeps track of each node's position
so I'm working on a lab for my class. I need to create a Priority Queue in Java using an array list. The kicker is that each node has to have a "handle" which is just an object which contains the index of of the node that it's associated with. I know that sounds weird but we have to implement it this way. Anyway, my priority queue seem to work fine except the handle values apparently aren't updating correctly because I fail the handle test. Also, I run into problems with handles only after extractMin() is called, so I figured the problem would be somewhere in that method but I've been through it a million times and it looks good to me.
Here is my Priority Queue Class:
package lab3; import java.util.ArrayList; /** * A priority queue class supporting operations needed for * Dijkstra's algorithm. */ class PriorityQueue<T> { final static int INF = 1000000000; ArrayList<PQNode<T>> queue; /** * Constructor */ public PriorityQueue() { queue = new ArrayList<PQNode<T>>(); } /** * @return true iff the queue is empty. */ public boolean isEmpty() { if (queue.size() <= 0) return true; return false; } /** * Insert a (key, value) pair into the queue. * * @return a Handle to this pair so that we can find it later. */ Handle insert(int key, T value) { queue.add(new PQNode(key, value)); int loc = queue.size()-1; // Swap with parent until parent not larger while (loc > 0 && queue.get(loc).getKey() < queue.get(parent(loc)).getKey()) { swap(loc, parent(loc)); loc = parent(loc); } return new Handle(loc); } private void swap(int i, int j) { PQNode t = queue.get(i); queue.set(i, queue.get(j)); queue.get(i).setHandleIndex(i); queue.set(j, t); queue.get(j).setHandleIndex(j); } /** * @return the min key in the queue. */ public int min() { if (isEmpty()) return -INF; return queue.get(0).getKey(); } /** * Find and remove the smallest (key, value) pair in the queue. * * @return the value associated with the smallest key */ public T extractMin() { if (isEmpty()) return null; else{ T value = queue.get(0).getValue(); swap(0, queue.size()-1); queue.get(queue.size()-1).setHandleIndex(-1); queue.remove(queue.size()-1); heapify(0); return value; } } private void heapify(int i) { int left = leftChild(i); int right = rightChild(i); int min; if (left <= queue.size()-1 && queue.get(left).getKey() < queue.get(i).getKey()) min = left; else min = i; if (right <= queue.size()-1 && queue.get(right).getKey() < queue.get(min).getKey()) min = right; if (min != i){ swap(i, min); heapify(min); } } private static int parent(int i) { return (i-1)/2; } private static int leftChild(int i) { return 2*i + 1; }
And my PQNode Class:
package lab3; public class PQNode<T> { int key; T value; Handle handle; PQNode(int k, T v){ key = k; value = v; handle = new Handle(0); } /** * @return the key */ public int getKey() { return key; } /** * @param key the key to set */ public void setKey(int key) { this.key = key; } /** * @return the value */ public T getValue() { return value; } /** * @param value the value to set */ public void setValue(T value) { this.value = value; } public void setHandle(Handle handle){ this.handle = handle; } /** * @return the handle */ public Handle getHandle() { return handle; } public int getHandleIndex(){ return handle.getIndex(); } public void setHandleIndex(int i){ handle.setIndex(i); } }
And my Handle Class:
package lab3; public class Handle { int index; public Handle(int i) { index = i; } /** * @return the index */ public int getIndex() { return index; } /** * @param index the index to set */ public void setIndex(int index) { this.index = index; } }
I can post the tests too if you'd like but I don't know if that would do much good. Just know that the queue works as is should, but the handles don't point to the right nodes after extractMin() is utilized. Please tell me if you'd like more information, I know this is all a little vague. Thanks so much guys.
Reply With Quote
Related threads:
Re: Priority Queue in Java which keeps track of each node's position
