com.mhhe.clrs2e
Interface MinPriorityQueue

All Known Implementing Classes:

MinHeapPriorityQueue

public interface MinPriorityQueue

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

Method Summary

void	decreaseKey(java.lang.Object element, java.lang.Comparable newKey) Decreases the key of a given element to a new value.
com.mhhe.clrs2e.DynamicSetElement	extractMin() Removes and returns the smallest element in the min-priority queue.
java.lang.Object	insert(com.mhhe.clrs2e.DynamicSetElement x) Inserts a dynamic-set element into the min-priority queue.
boolean	isEmpty() Returns true if the min-priority queue is empty, false if non-empty.
com.mhhe.clrs2e.DynamicSetElement	minimum() Returns the smallest element in the min-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 min-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 a decreaseKey(java.lang.Object, java.lang.Comparable) operation.

minimum

public com.mhhe.clrs2e.DynamicSetElement minimum()

Returns the smallest element in the min-priority queue without removing the element.

extractMin

public com.mhhe.clrs2e.DynamicSetElement extractMin()

Removes and returns the smallest element in the min-priority queue.

In order for the handle of the element returned to be eligible for garbage collection, the user of the MinPriorityQueue 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 extractMin.

decreaseKey

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

Decreases 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 greater than the current key value.

isEmpty

public boolean isEmpty()

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