edu.stanford.nlp.util
Interface Heap

All Known Implementing Classes:

ArrayHeap

public interface Heap

Heap: It's the heap interface. These heaps implement a decreaseKey operation, which requires a separate Object to Index map, and for objects to be unique in the Heap. An interface cannot specify constructors, but it is nevertheless expected that an implementation of this interface has a constructor that takes a Comparator, which is used for ordering ("scoring") objects: public Heap(Comparator cmp) {}

Method Summary

void	add(Object o) Adds the object to the heap.
int	decreaseKey(Object o) Raises the priority of an object in the heap.
Object	extractMin() Returns the minimum object, then removes that object from the heap.
boolean	isEmpty() Returns true iff the heap is empty.
Object	min() Returns the minimum Object in this heap.
int	size() The number of elements currently in the heap.

Method Detail

extractMin

public Object extractMin()

Returns the minimum object, then removes that object from the heap.

Returns:

the minimum object

min

public Object min()

Returns the minimum Object in this heap. The heap is not modified.

Returns:

the minimum object

add

public void add(Object o)

Adds the object to the heap. If the object is in the heap, this should act as a decrease-key (if the new version has better priority) or a no-op (otherwise).

Parameters:

o - a new element

size

public int size()

The number of elements currently in the heap.

Returns:

the heap's size

isEmpty

public boolean isEmpty()

Returns true iff the heap is empty.

Returns:

a boolean value

decreaseKey

public int decreaseKey(Object o)

Raises the priority of an object in the heap. This works in a somewhat unusual way -- the object o should have changed with respect to the comparator passed in to the heap on construction. However, it should NOT have changed with respect to its equals() method. This is unlike the Java SortedSet where the comparator should be consistent with equals(); here they should not match.

Parameters:

o - an Object value which has changed wrt the heap's ordering

Returns:

the cost of the decrease-key operation, for analysis