我正在尝试实现一个优先级队列,它的功能与普通的优先级队列有点不同。这里的想法是支持快速插入,但对最高优先级项目的访问较慢。在这种情况下,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()方法工作
实现这一点的最简单方法是使用<code>java.util。列表而不是数组
。因此,列表
将保留队列中的元素,并处理它们的定位,而不对它们进行排序(因此它仍然使用快速插入)。如果使用实现<code>java.util。ArrayList对于<code>List,因此它几乎与您所尝试的一样,但更容易,因为其他人已经完成了大部分工作。。。
因此,您可以像这样实现类最小优先级队列
:
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
我正在编写一个涉及堆实现的代码,在我的bubbleUp方法中,在我的while循环行中,我似乎遇到了一个取消引用的错误。这可能是一个相当基本的问题,但解决这个问题的最佳方法是什么?我在实现removeHigh方法时也遇到了一些问题,该方法旨在从队列中移除最高的元素。
我看到的替换优先级队列比较器的公认答案是在新的比较类中重载操作符。 然而,我想为队列实现几个(10)不同的比较函数,并在运行时在main()中创建pq时选择一个。我必须做10个不同的比较类还是有更简单的方法来做到这一点?
问题 怎样实现一个按优先级排序的队列? 并且在这个队列上面每次 pop 操作总是返回优先级最高的那个元素 解决方案 下面的类利用 heapq 模块实现了一个简单的优先级队列: import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index = 0
在谷歌搜索了几天之后,我相信我完全迷路了。我想实现一种优先级队列,它大约有3个队列: 高优先级队列(每日),需要先处理 中等优先级队列(每周),如果队列#1中没有项目,将进行处理。(此队列中的ok消息根本不处理) 低优先级队列(每月),如果队列#1中没有项目,将进行处理 最初,我有以下流程,让消费者使用所有三个队列中的消息,并检查队列#1、#2和#3中是否有任何项目。然后我意识到这是错误的,因为:
我想实现一个具有以下约束的双端优先级队列: > 需要在固定大小的数组中实现。例如100个元素。如果在数组已满后需要添加新元素,则需要删除最旧的元素 需要最大和最小的O(1) 如有可能,插入O(1) 如果可能,去掉O(1)中的最小值 如果可能,清除O(1)中的空/初始化状态 O(1)中当前数组中元素的个数 我希望 O(1) 用于上述所有 5 个操作,但不可能在同一实现中对所有这些操作使用 O(1)。
我目前正在尝试实现min heap PQ,但是我在实现的正确性方面遇到了一些问题,我似乎无法找出我做错了什么——它没有输出最低优先级,也没有对它们进行正确排序。 使用以下测试数据: 我得到以下结果: 我希望结果是按升序排列的——起初我认为这可能是因为交换了错误的孩子,但最后一个输出是最大的优先级,所以这没有意义。我花了几个小时试图研究堆优先级队列,但我找不到任何帮助。 以下是CMP要求的更好的代码