I have a remove method in a Priority Queue class I created from scratch for an assignment. The priority queue I created is held in an array, with the index starting at 0. I keep track of size which is equal to the arrays length. The remove method uses a helper method entitled:
public int findSmallest(int parent)
where parent is the position in the array that the parent is stored at, and I am looking to return its smallest child. Order is simply the number of children each node that is not a leaf has. The code for my findSmallest:
public int findSmallest(int parent) {
int child = parent * order + 1;
int smallest = child;
for (int i = child; i < order + child; ++i) {
if (size >= i) {
return child;
}
if (queue[i].priority <= queue[smallest].priority) {
smallest = child;
}
}
return child;
}
It is currently an array out of bounds exception Complete implementation of PriorityQueue Class I created:
import java.util.*;
public class PriorityQueue {
private class Item {
private int priority;
private Object data;
private Item(int p, Object d) {
priority = p;
data = d;
}
}
private Item queue[];
private int order;
private int size;
public PriorityQueue(int ord, int s) {
queue = new Item[s];
order = ord;
size = 0;
}
public int getPriority() {
if (size > 0) {
return queue[0].priority;
}
// -55 signifies that the queue is empty
return -55;
}
public Object getData() {
if (size > 0) {
return queue[0].priority;
}
return null;
}
public void remove() {
if (empty() == true) {
System.out.println("Queue is empty, there is nothing to remove.");
return;
}
Item x = queue[size - 1];
size--;
int child = 1;
int parent = 0;
while (child <= size) {
child = findSmallest(parent);
for (int i = order * parent + 1; i < child + order; i++) {
if (child < size && queue[i].priority < queue[child].priority)
child = i;
}
if (x.priority < queue[child].priority)
break;
else {
parent = child;
queue[(child - 1) / order] = queue[child];
child = order * child + 1;
}
}
queue[(child - 1) / order] = x;
}
public int findSmallest(int parent) {
int child = parent * order + 1;
int smallest = child;
for (int i = child; i < order + child; ++i) {
if (size >= i) {
return child;
}
if (queue[i].priority <= queue[smallest].priority) {
smallest = child;
}
}
return child;
}
public int getSize() {
return size;
}
public boolean full() {
return size == queue.length;
}
public boolean empty() {
if (size > 0) {
return false;
}
return true;
}
public void insert(int p, Object d) {
// 1. Create a new Item and add it to queue[size]
// Somewhere store new node created as TEMP
// 2. while loop
// 3. check if node has parent
// 4. if it does --> check if parent.priority > child.priority
// 5. if yes, swap
if (full() == true) {
System.out.println("Queue is full, cannot add new node.");
return;
}
queue[size] = new Item(p, d);
sort();
size++;
}
// Sort() swaps new child node with parents if child.priority < parent.priority
public void sort() {
int child = size;
Item temp = queue[child];
while ( child > 0 && queue[child].priority < queue[(child-1)/(order)].priority) {
queue[child] = queue[(child-1)/order];
queue[(child-1)/order] = temp;
child = ((child - 1) / order);
}
queue[child] = temp;
}
public static void main(String[] args) {
PriorityQueue p1 = new PriorityQueue(5, 100);
PriorityQueue p2 = new PriorityQueue(6, 100);
PriorityQueue p3 = new PriorityQueue(7, 100);
int p = -1; //pointless initialization to keep the compiler happy
p1.insert(0, new Integer(0));
System.out.println("First insert");
for (int i = 1; i < 100; i++)
p1.insert(i, new Integer(i));
for (int i = 0; i < 100; i++)
p2.insert(i, new Integer(i));
for (int i = 0; i < 100; i++)
p3.insert(i, new Integer(i));
System.out.println("First insert tests");
System.out.print(p1.getPriority()+",");
while (!p1.empty()) {
p = p1.getPriority();
Object d = p1.getData();
p1.remove();
}
System.out.println(p);
System.out.print(p2.getPriority()+",");
while (!p2.empty()) {
p = p2.getPriority();
Object d = p2.getData();
p2.remove();
}
System.out.println(p);
System.out.print(p3.getPriority()+",");
while (!p3.empty()) {
p = p3.getPriority();
Object d = p3.getData();
p3.remove();
}
System.out.println(p);
System.out.println("First Remove Test");
for (int i = 100; i > 0 ; i--)
p1.insert(i, new Integer(i));
for (int i = 100; i > 0 ; i--)
p2.insert(i, new Integer(i));
for (int i = 100; i > 0 ; i--)
p3.insert(i, new Integer(i));
System.out.println("Second insert tests");
System.out.print(p1.getPriority()+",");
while (!p1.empty()) {
p = p1.getPriority();
Object d = p1.getData();
p1.remove();
}
System.out.println(p);
System.out.print(p2.getPriority()+",");
while (!p2.empty()) {
p = p2.getPriority();
Object d = p2.getData();
p2.remove();
}
System.out.println(p);
System.out.print(p3.getPriority()+",");
while (!p3.empty()) {
p = p3.getPriority();
Object d = p3.getData();
p3.remove();
}
System.out.println(p);
System.out.println("Second Remove Test");
Random r1 = new Random(1000);
while (!p3.full()) {
p = r1.nextInt(200);
System.out.print(p+",");
p3.insert(p, new Integer(p));
}
System.out.println();
while (!p3.empty()) {
System.out.print(p3.getPriority()+",");
Object d = p3.getData();
p3.remove();
}
System.out.println();
System.out.println("Third Remove Test");
}
}
Main includes 3 different ways I am testing my code.
If your problem is just with the findSmallest method, here is the solution:
public int findSmallest( int parent ) {
int smallestChild = -1;
int firstChild = parent * order + 1;
int lastChild = parent * order + order;
int currentSmallestChild = firstChild;
for ( int i = firstChild + 1; i <= lastChild; i++ ) {
if ( i > size || queue[i] == null ) {
break;
}
if ( queue[currentSmallestChild].priority > queue[i].priority ) {
currentSmallestChild = i;
smallestChild = i;
}
}
return smallestChild;
}
It will return -1 if there is not a smallest child. This code can be improved, I let it this way because I think it is easier to understand. Let me know if it works.