Reputation: 81
Trying to Implement a priority queue in a different way
I am trying to implement a priority queue which functions a little bit different than normal priority queue.Here,the idea is to support fast insert, but slower access to the highest priority item. Insert method in this case places the new item wherever it is convenient;remove and peek methods must thus search through the entire queue for the highest priority item.
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 File
/**
* 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();
}
}
I have been able to implement all methods except remove and peek because i am unable to get the logic right to implement the methods.I am unable to figure out how we can search the entire queue to find the highest priority item.For this,i believe for loop should be used,but just not getting the logic right
EDIT : I am able to get the logic right for remove() method,just need to get the pop() method to work
Upvotes: 2
Views: 284
Answers (1)
Reputation: 2575
The easiest way to achieve this is to use a java.util.List instead of an array. So the List will keep the elements in the queue and handle the positioning of them without sorting them (so it still uses a fast insert). If you use the implementation java.util.ArrayList for the List interface it uses an array internally so it's almost exactly what you were trying but easier, because someone else has already done most of the work...
So you could implement the class MinPriorityQueue like this:
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);
}
}
This code passes all of the test cases you provided in your question.
I also added a generic type argument in the example code (therefore the class declaration is now MinPriorityQueue<T extends Comparable<T>>), because it was needed to actually compare the elements. You can check about generic types here.
Upvotes: 3