gpt4 book ai didi

java - 尝试以不同的方式实现优先级队列

转载 作者:行者123 更新时间:2023-11-30 07:40:10 26 4
gpt4 key购买 nike

我正在尝试实现一个优先级队列,它的功能与普通优先级队列有点不同。这里的想法是支持快速插入,但对最高优先级项目的访问速度较慢。在这种情况下,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 之外的所有方法,因为我无法获得实现这些方法的正确逻辑。我无法弄清楚我们如何搜索整个队列以找到最高优先级的项目。对于这个,我认为应该使用 for 循环,但逻辑不正确

编辑:我能够获得 remove() 方法的正确逻辑,只需要让 pop() 方法工作

最佳答案

实现此目的的最简单方法是使用 java.util.List而不是 array .所以 List会将元素保留在队列中并处理它们的定位而不对它们进行排序(因此它仍然使用快速插入)。如果你使用实现 java.util.ArrayList对于 List它使用 array 的界面在内部,所以这几乎正是你正在尝试的,但更容易,因为其他人已经完成了大部分工作......

所以你可以实现类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);
}
}

此代码通过了您在问题中提供的所有测试用例。

我还在示例代码中添加了一个泛型类型参数(因此类声明现在是 MinPriorityQueue<T extends Comparable<T>> ),因为它需要实际比较元素。您可以检查泛型类型 here .

关于java - 尝试以不同的方式实现优先级队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58073288/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com