Worksheet 4

The aim of this workshop is to define a delete method for priority queues implemented by binary heaps.

The PriorityQueue interface discussed in lectures is just

public interface PriorityQueue {
    public boolean isEmpty();
    public int size();
    public void add(Comparable item);
    public Comparable remove();
}

The main methods are just add and remove. The remove method returns the item of highest priority from the queue and dequeues it. It is possible, however, that you might want to delete an item from the queue, e.g. a print job that you wish to cancel before it appears as the item of highest priority. Let us call this

public void delete(Comparable item);

and agree that if the item is not in the queue, nothing needs to be done.

The file MyPriorityQueue.java just extends the PriorityQueue interface by this single method. Your task is to implement this extended interface. All you have to do is to implement the single new delete method.

To help you, the file MyBinaryHeap.java implements all the methods apart from the new one. You have to add the code in the place indicated. You may find the file MyPriorityQueueDemo.java useful in checking your implementation. Copy all these files to your working area and then go to work.

You will find that the implementation of the remove method has also been changed by introducing the private demote method. We encountered this in the HeapSort method. The remove method now calls the demote method. The reason for this is that you may find the demote method helpful in implementing the new delete method.

You will have to go through the heap array looking for the item to be deleted. Once you have found it, replace it by the last element in the heap and then restore heap order. You may find that your code looks very similar to the code for remove.

Assuming you have done that, now think about the following questions.

1. What is the complexity of this delete operation?
2. Can you think of any more efficient method?
3. Think about implementing an Enumeration over the priority queue which lists the elements in order of priority. Better still, do it! (You will need to change the interface as well).
4. Does it make sense to use an Iterator that has its own remove method (which would correspond to our new delete method)? The problem is that restoring heap order after any deletion rearranges the underlying heap array? Can you think of any way of overcoming this problem?