嗨,所以即时在项目上工作,我的出队最小值首先似乎有问题。它似乎入列罚款。在20,15,11,29中打出正确的11,20,15,29。这些数字符合要达到的期限。现在,当我想取出最高值时,它会抓取11个需要的操作,并放弃截止日期为11的任务。然后,当我抓取下一个顶部值时,返回20而不是15。为什么?任何帮助将不胜感激!在Java中出队的优先级队列问题
import java.util.Comparator;
public class treeCompare implements Comparator<Task> {
public int compare(Task t1, Task t2) {
int dead1 = t1.getDeadline();
int dead2 = t2.getDeadline();
return dead1 - dead2;
}
}
import java.util.ArrayList;
import java.util.Comparator;
public class PriorityQueue<E> implements QueueADT<E> {
private ArrayList<E> items;
private int max;
private Comparator<E> comp;
public PriorityQueue(Comparator<E> comp, int maxCapacity){
this.comp = comp;
this.max = maxCapacity;
items = new ArrayList<E>();
}
public boolean isFull() {
if(size() == max) return true;
else return false;
}
private void siftUp() {
int k = items.size() - 1;
while (k > 0) {
int p = (k-1)/2;
E item = items.get(k);
E parent = items.get(p);
if (comp.compare(items.get(k), items.get(p)) < 0) {
// swap
items.set(k, parent);
items.set(p, item);
// move up one level
k = p;
} else {
break;
}
}
}
public void enqueue(E item)throws FullQueueException {
if(isFull()) throw new FullQueueException();
items.add(item);
siftUp();
}
/**
* Returns the front item of the queue without removing it.
* @return the front item of the queue
* @throws EmptyQueueException
*/
public E peek() throws EmptyQueueException {
if(isEmpty()) throw new EmptyQueueException();
else{
E item = items.get(0);
return item;
}
}
private void siftDown() {
int k = 0;
int l = 2*k+1;
while (l < items.size()) {
int max=l, r=l+1;
if (r < items.size()) { // there is a right child
if (comp.compare(items.get(r), items.get(l)) > 0) {
max++;
}
}
if (comp.compare(items.get(k), items.get(max)) > 0) {
// switch
E temp = items.get(k);
items.set(k, items.get(max));
items.set(max, temp);
k = max;
l = 2*k+1;
} else {
break;
}
}
}
public E dequeue() throws EmptyQueueException {
if (items.size() == 0) {
throw new EmptyQueueException();
}
if (items.size() == 1) {
return items.remove(0);
}
E hold = items.get(0);
items.set(0, items.remove(items.size()-1));
siftDown();
return hold;
}
public int size() {
return items.size();
}
public boolean isEmpty() {
return items.isEmpty();
}
public String toString() {
return items.toString();
}
public int capacity() {
return max;
}
}
使用调试器。 –
为什么你不使用JDK的'PriorityQueue'? – fge
作业的目的之一是编码我们自己的优先级队列 – RunFranks525