com.mhhe.clrs2e
Interface MaxPriorityQueue

All Known Implementing Classes:

MaxHeapPriorityQueue

public interface MaxPriorityQueue

Interface for a max-priority queue. In classes that implement this interface, the constructor should create an empty max-priority queue.

Method Summary

com.mhhe.clrs2e.DynamicSetElement	extractMax() Removes and returns the largest element in the max-priority queue.
void	increaseKey(java.lang.Object element, java.lang.Comparable newKey) Increases the key of a given element to a new value.
java.lang.Object	insert(com.mhhe.clrs2e.DynamicSetElement x) Inserts a dynamic-set element into the max-priority queue.
boolean	isEmpty() Returns true if the max-priority queue is empty, false if non-empty.
com.mhhe.clrs2e.DynamicSetElement	maximum() Returns the largest element in the max-priority queue without removing the element.

Method Detail

insert

public java.lang.Object insert(com.mhhe.clrs2e.DynamicSetElement x)

Inserts a dynamic-set element into the max-priority queue.

Parameters:

x - The dynamic-set element to be inserted.

Returns:

A handle to the inserted item. This handle is how the item is accessed in an increaseKey(java.lang.Object, java.lang.Comparable) operation.

maximum

public com.mhhe.clrs2e.DynamicSetElement maximum()

Returns the largest element in the max-priority queue without removing the element.

extractMax

public com.mhhe.clrs2e.DynamicSetElement extractMax()

Removes and returns the largest element in the max-priority queue.

In order for the handle of the element returned to be eligible for garbage collection, the user of the MaxPriorityQueue should include in a DynamicSetElement's satellite data a reference to the handle. This reference should be set to null for the element returned by extractMax.

increaseKey

public void increaseKey(java.lang.Object element,
                        java.lang.Comparable newKey)
                 throws KeyUpdateException

Increases the key of a given element to a new value.

Parameters:

element - Handle identifying the element; this handle is initially given as the return value of insert(com.mhhe.clrs2e.DynamicSetElement).

newKey - The new key value for this element.

Throws:

KeyUpdateException - if the new key value is less than the current key value.

isEmpty

public boolean isEmpty()

Returns true if the max-priority queue is empty, false if non-empty.