尝试以不同的方式实现优先级队列
Trying to Implement a priority queue in a different way
我正在尝试实现一个优先级队列，它的功能与普通优先级稍有不同 queue.Here，其想法是支持快速插入，但对最高优先级项目的访问速度较慢。在这种情况下，Insert 方法将新项目放在方便的地方；因此，remove 和 peek 方法必须在整个队列中搜索最高优先级的项目。
public class MinPriorityQueue {
/** Constructs a new MinPriorityQueue with capacity cap and size 0.
*
* @param cap Capacity of the new queue.
*/
public MinPriorityQueue(int cap) {
this.queue = (Comparable []) new Comparable[cap];
this.size = 0;
this.cap = cap;
}
int size() {
return this.size;
}
int capacity() {
return this.cap;
}
boolean isEmpty() {
return this.size==0;
}
boolean isFull() {
return this.size == cap;
}
void insert(Comparable e) {
if (this.size == cap) {
throw new IllegalStateException();
}
queue[size] = e;
size++;
Comparable remove() {
if (this.size == 0) {
throw new IllegalStateException();
}
int maxIndex = 0;
for (int i=1; i<size; i++) {
if (queue[i].compareTo (queue[maxIndex]) < 0) {
maxIndex = i;
}
}
Comparable result = queue[maxIndex];
size--;
queue[maxIndex] = queue[size];
return result;
}
/** Returns, but does not remove, the lowest-priority item in the
* queue.
*
* Complexity: O(n)
* @return Lowest priority item.
* @throws IllegalStateException if the queue is empty.
*/
Comparable top() {
if (this.size == 0) {
throw new IllegalStateException();
}
/* int i;
for (i=0; i < size; i++) {
if (queue[i].compareTo (size-1) < 0) {
break;
}
}
return queue[size - 1];*/
return queue[size-1];
}
Comparable[] queue; // Contents of the queue
private int cap;
private int size;
}
//// 测试文件
/**
* Test of remove method, of class MinPriorityQueue.
*/
@Test
public void testRemove() {
System.out.println("remove");
MinPriorityQueue q = new MinPriorityQueue(10);
boolean throws_exception = false;
try {
q.remove();
} catch (IllegalStateException e) {
throws_exception = true;
} catch (Throwable e) {
}
assertTrue("remove throws an exception when empty", throws_exception);
// Permutation of 0...9
int[] input = {0, 5, 9, 2, 3, 1, 6, 8, 7, 4};
for (int i : input) {
q.insert(i);
}
assertTrue(q.isFull());
for (int i = 10; i > 0; --i) {
assertEquals(q.size(), i);
Integer x = (Integer) q.remove();
assertEquals(x, new Integer(10 - i)); // Items are removed in correct order
}
assertTrue(q.isEmpty());
}
/**
* Test of top method, of class MinPriorityQueue.
*/
@Test
public void testTop() {
System.out.println("top");
MinPriorityQueue q = new MinPriorityQueue(10);
boolean throws_exception = false;
try {
q.top();
} catch (IllegalStateException x) {
throws_exception = true;
} catch (Throwable x) {
}
assertTrue("top throws an exception when empty", throws_exception);
int[] input = {0, 5, 9, 2, 3, 1, 6, 8, 7, 4};
int smallest = 10;
for (int i : input) {
q.insert(i);
if (i < smallest) {
smallest = i;
}
assertEquals(q.top(), smallest);
}
for (int i = 0; i < 10; ++i) {
assertEquals(q.top(), i);
q.remove();
}
}
我已经能够实现除 remove 和 peek 之外的所有方法，因为我无法获得正确的逻辑来实现 methods.I 我无法弄清楚我们如何搜索整个队列以找到最高的priority item.For 这个，我认为应该使用 for 循环，但逻辑不正确
编辑：我能够获得 remove() 方法的正确逻辑，只需要让 pop() 方法工作
实现此目的的最简单方法是使用 java.util.List 而不是 array。所以 List 会将元素保留在队列中并处理它们的定位而不对它们进行排序（因此它仍然使用快速插入）。如果您对 List 接口使用 java.util.ArrayList 实现，它会在内部使用 array 所以它几乎正是您正在尝试的，但更容易，因为其他人已经完成了大部分工作.. .
所以你可以像这样实现 class MinPriorityQueue：
import java.util.ArrayList;
import java.util.List;
//use a generic type argument T here that extends comparable so you can only store objects of a specific type that are comparable to each other
public class MinPriorityQueue<T extends Comparable<T>> {
private List<T> queue; // Contents of the queue
private int cap;
//private int size;
/**
* Constructs a new MinPriorityQueue with capacity cap and size 0.
*
* @param cap
* Capacity of the new queue.
*/
public MinPriorityQueue(int cap) {
this.queue = new ArrayList<T>(cap);
//this.size = 0;
this.cap = cap;
}
public int size() {
//return this.size;
return queue.size();
}
public int capacity() {
return this.cap;
}
public boolean isEmpty() {
//return this.size == 0;
return queue.isEmpty();
}
public boolean isFull() {
//return this.size == cap;
return queue.size() == cap;
}
public void insert(T e) {
if (queue.size() == cap) {
throw new IllegalStateException();
}
//queue[size] = e;
//size++;
queue.add(e);
}
/**
* Removes and returns the lowest-priority item from the queue.
*
* Complexity: O(n)
*
* @return Lowest priority item that was in the queue.
* @throws IllegalStateException
* if the queue is empty.
*/
public Comparable<T> remove() {
if (queue.size() == 0) {
throw new IllegalStateException();
}
/*for (int i = 0; i < this.size; i++) {
if (this.queue[i] == queue[size]) {
return i;
}
}
return queue[--size];*/
//initialize the lowest priority item with the first one in the list
int lowestPriorityIndex = 0;
//search every other item in the list to see whether it has a lower priority than the current lowest priority
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i).compareTo(queue.get(lowestPriorityIndex)) < 0) {
lowestPriorityIndex = i;
}
}
//return and remove the lowest priority item
return queue.remove(lowestPriorityIndex);
}
/**
* Returns, but does not remove, the lowest-priority item in the queue.
*
* Complexity: O(n)
*
* @return Lowest priority item.
* @throws IllegalStateException
* if the queue is empty.
*/
public Comparable<T> top() {
if (queue.size() == 0) {
throw new IllegalStateException();
}
/* int i;
for (i=0; i < size; i++) {
if (queue[i].compareTo (size-1) < 0) {
break;
}
}
return queue[size - 1];*/
//initialize the lowest priority item with the first one in the list
int lowestPriorityIndex = 0;
//search every other item in the list to see whether it has a lower priority than the current lowest priority
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i).compareTo(queue.get(lowestPriorityIndex)) < 0) {
lowestPriorityIndex = i;
}
}
//return (but not remove) the lowest priority item
return queue.get(lowestPriorityIndex);
}
}
此代码通过了您在问题中提供的所有测试用例。
我还在示例代码中添加了一个泛型类型参数（因此 class 声明现在是 MinPriorityQueue<T extends Comparable<T>>），因为它需要实际比较元素。您可以检查泛型类型 here.
我正在尝试实现一个优先级队列，它的功能与普通优先级稍有不同 queue.Here，其想法是支持快速插入，但对最高优先级项目的访问速度较慢。在这种情况下，Insert 方法将新项目放在方便的地方；因此，remove 和 peek 方法必须在整个队列中搜索最高优先级的项目。
public class MinPriorityQueue {
/** Constructs a new MinPriorityQueue with capacity cap and size 0.
*
* @param cap Capacity of the new queue.
*/
public MinPriorityQueue(int cap) {
this.queue = (Comparable []) new Comparable[cap];
this.size = 0;
this.cap = cap;
}
int size() {
return this.size;
}
int capacity() {
return this.cap;
}
boolean isEmpty() {
return this.size==0;
}
boolean isFull() {
return this.size == cap;
}
void insert(Comparable e) {
if (this.size == cap) {
throw new IllegalStateException();
}
queue[size] = e;
size++;
Comparable remove() {
if (this.size == 0) {
throw new IllegalStateException();
}
int maxIndex = 0;
for (int i=1; i<size; i++) {
if (queue[i].compareTo (queue[maxIndex]) < 0) {
maxIndex = i;
}
}
Comparable result = queue[maxIndex];
size--;
queue[maxIndex] = queue[size];
return result;
}
/** Returns, but does not remove, the lowest-priority item in the
* queue.
*
* Complexity: O(n)
* @return Lowest priority item.
* @throws IllegalStateException if the queue is empty.
*/
Comparable top() {
if (this.size == 0) {
throw new IllegalStateException();
}
/* int i;
for (i=0; i < size; i++) {
if (queue[i].compareTo (size-1) < 0) {
break;
}
}
return queue[size - 1];*/
return queue[size-1];
}
Comparable[] queue; // Contents of the queue
private int cap;
private int size;
}
//// 测试文件
/**
* Test of remove method, of class MinPriorityQueue.
*/
@Test
public void testRemove() {
System.out.println("remove");
MinPriorityQueue q = new MinPriorityQueue(10);
boolean throws_exception = false;
try {
q.remove();
} catch (IllegalStateException e) {
throws_exception = true;
} catch (Throwable e) {
}
assertTrue("remove throws an exception when empty", throws_exception);
// Permutation of 0...9
int[] input = {0, 5, 9, 2, 3, 1, 6, 8, 7, 4};
for (int i : input) {
q.insert(i);
}
assertTrue(q.isFull());
for (int i = 10; i > 0; --i) {
assertEquals(q.size(), i);
Integer x = (Integer) q.remove();
assertEquals(x, new Integer(10 - i)); // Items are removed in correct order
}
assertTrue(q.isEmpty());
}
/**
* Test of top method, of class MinPriorityQueue.
*/
@Test
public void testTop() {
System.out.println("top");
MinPriorityQueue q = new MinPriorityQueue(10);
boolean throws_exception = false;
try {
q.top();
} catch (IllegalStateException x) {
throws_exception = true;
} catch (Throwable x) {
}
assertTrue("top throws an exception when empty", throws_exception);
int[] input = {0, 5, 9, 2, 3, 1, 6, 8, 7, 4};
int smallest = 10;
for (int i : input) {
q.insert(i);
if (i < smallest) {
smallest = i;
}
assertEquals(q.top(), smallest);
}
for (int i = 0; i < 10; ++i) {
assertEquals(q.top(), i);
q.remove();
}
}
我已经能够实现除 remove 和 peek 之外的所有方法，因为我无法获得正确的逻辑来实现 methods.I 我无法弄清楚我们如何搜索整个队列以找到最高的priority item.For 这个，我认为应该使用 for 循环，但逻辑不正确
编辑：我能够获得 remove() 方法的正确逻辑，只需要让 pop() 方法工作
实现此目的的最简单方法是使用 java.util.List 而不是 array。所以 List 会将元素保留在队列中并处理它们的定位而不对它们进行排序（因此它仍然使用快速插入）。如果您对 List 接口使用 java.util.ArrayList 实现，它会在内部使用 array 所以它几乎正是您正在尝试的，但更容易，因为其他人已经完成了大部分工作.. .
所以你可以像这样实现 class MinPriorityQueue：
import java.util.ArrayList;
import java.util.List;
//use a generic type argument T here that extends comparable so you can only store objects of a specific type that are comparable to each other
public class MinPriorityQueue<T extends Comparable<T>> {
private List<T> queue; // Contents of the queue
private int cap;
//private int size;
/**
* Constructs a new MinPriorityQueue with capacity cap and size 0.
*
* @param cap
* Capacity of the new queue.
*/
public MinPriorityQueue(int cap) {
this.queue = new ArrayList<T>(cap);
//this.size = 0;
this.cap = cap;
}
public int size() {
//return this.size;
return queue.size();
}
public int capacity() {
return this.cap;
}
public boolean isEmpty() {
//return this.size == 0;
return queue.isEmpty();
}
public boolean isFull() {
//return this.size == cap;
return queue.size() == cap;
}
public void insert(T e) {
if (queue.size() == cap) {
throw new IllegalStateException();
}
//queue[size] = e;
//size++;
queue.add(e);
}
/**
* Removes and returns the lowest-priority item from the queue.
*
* Complexity: O(n)
*
* @return Lowest priority item that was in the queue.
* @throws IllegalStateException
* if the queue is empty.
*/
public Comparable<T> remove() {
if (queue.size() == 0) {
throw new IllegalStateException();
}
/*for (int i = 0; i < this.size; i++) {
if (this.queue[i] == queue[size]) {
return i;
}
}
return queue[--size];*/
//initialize the lowest priority item with the first one in the list
int lowestPriorityIndex = 0;
//search every other item in the list to see whether it has a lower priority than the current lowest priority
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i).compareTo(queue.get(lowestPriorityIndex)) < 0) {
lowestPriorityIndex = i;
}
}
//return and remove the lowest priority item
return queue.remove(lowestPriorityIndex);
}
/**
* Returns, but does not remove, the lowest-priority item in the queue.
*
* Complexity: O(n)
*
* @return Lowest priority item.
* @throws IllegalStateException
* if the queue is empty.
*/
public Comparable<T> top() {
if (queue.size() == 0) {
throw new IllegalStateException();
}
/* int i;
for (i=0; i < size; i++) {
if (queue[i].compareTo (size-1) < 0) {
break;
}
}
return queue[size - 1];*/
//initialize the lowest priority item with the first one in the list
int lowestPriorityIndex = 0;
//search every other item in the list to see whether it has a lower priority than the current lowest priority
for (int i = 1; i < queue.size(); i++) {
if (queue.get(i).compareTo(queue.get(lowestPriorityIndex)) < 0) {
lowestPriorityIndex = i;
}
}
//return (but not remove) the lowest priority item
return queue.get(lowestPriorityIndex);
}
}
此代码通过了您在问题中提供的所有测试用例。
我还在示例代码中添加了一个泛型类型参数（因此 class 声明现在是 MinPriorityQueue<T extends Comparable<T>>），因为它需要实际比较元素。您可以检查泛型类型 here.