I had to implement this Priority queue interface with an ordered array. for example say I have an array of 5 4 3 3 3 2 1 the 1 in index 6 has a higher priority than 5 at index zero. I am stuck with the delete method. The code on my delete method is an idea I have but it is probably not right. To delete the object getting passed in first I use binary search to locate it because it is a requirement but after that I am not to sure what to do. Say I want to delete all the 3's from the above array I use binary search to see if my array contains a 3 and then I need to delete all of them so that means my currSize (items in array) become less. Here are the instructions for the delete method:

// Deletes all instances of the parameter obj from the PQ if found, and

// returns true. Returns false if no match to the parameter obj is found.

public boolean delete(E obj);

public interface PriorityQueue> extends Iterable {

public static final int DEFAULT_MAX_CAPACITY = 1000;

// Inserts a new object into the priority queue. Returns true if

// the insertion is successful. If the PQ is full, the insertion

// is aborted, and the method returns false.

public boolean insert(E object);

// Removes the object of highest priority that has been in the

// PQ the longest, and returns it. Returns null if the PQ is empty.

public E remove();

// Deletes all instances of the parameter obj from the PQ if found, and

// returns true. Returns false if no match to the parameter obj is found.

public boolean delete(E obj);

// Returns the object of highest priority that has been in the

// PQ the longest, but does NOT remove it.

// Returns null if the PQ is empty.

public E peek();

// Returns true if the priority queue contains the specified element

// false otherwise.

public boolean contains(E obj);

// Returns the number of objects currently in the PQ.

public int size();

// Returns the PQ to an empty state.

public void clear();

// Returns true if the PQ is empty, otherwise false

public boolean isEmpty();

// Returns true if the PQ is full, otherwise false. List based

// implementations should always return false.

public boolean isFull();

// Returns an iterator of the objects in the PQ, in no particular

// order.

public Iterator iterator();

}

package data_structures; import java.util.Iterator; import java.util.NoSuchElementException;

public class OrderedArrayPriorityQueue> implements PriorityQueue{ private int capacity, currSize; private E[] queue; public OrderedArrayPriorityQueue() { this(DEFAULT_MAX_CAPACITY); } public OrderedArrayPriorityQueue(int size) { currSize = 0; capacity = size; queue = (E[]) new Comparable[capacity]; } public boolean insert(E object) { if(isFull()) return false; if(isEmpty()) return false; int where = findInsertionPoint(object, 0, currSize-1); for(int i = currSize-1; i >= where; i--) { queue[i+1] = queue[i-1]; } queue[where] = object; currSize++; return true; } private int findInsertionPoint(E obj, int low, int high) { if(high < low) return low; int mid = (low+high)/2; if(((Comparable) obj).compareTo(queue[mid]) >= 0) return findInsertionPoint(obj, low, mid-1); return findInsertionPoint(obj, mid+1, high); } public E remove() { if(isEmpty()) return null; return queue[--currSize]; }

//Here's where I am stuck public boolean delete(E obj) { E temp; int pos = findInsertionPoint(obj, 0, currSize-1); for(int i = 0; i < currSize; i++) { if(obj.compareTo(queue[pos]) == 0) temp = queue[--pos]; return true; } return false; } public E peek() { if(isEmpty()) return null; return queue[currSize-1]; } public boolean contains(E obj) { int match = findInsertionPoint(obj, 0, currSize-1); if(obj.compareTo(queue[match]) == 0) return true; return false; } public int size() { return currSize; } public void clear() { currSize = 0; } public boolean isEmpty() { return currSize == 0; } public boolean isFull() { return currSize == capacity; } public Iterator iterator(){ return new IteratorHelper(); } private class IteratorHelper implements Iterator{ int index = 0; public boolean hasNext() { return (index < currSize); } public E next() { if(!hasNext()) { throw new NoSuchElementException(); } return (E) queue[index++]; } }

}