edu.stanford.nlp.util

Interface Heap<E>

All Known Implementing Classes:

ArrayHeap

public interface Heap<E>

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) {}

Author:

Dan Klein

Method Summary

Modifier and Type	Method and Description
boolean	add(E o) Adds the object to the heap.
int	decreaseKey(E o) Raises the priority of an object in the heap.
E	extractMin() Returns the minimum object, then removes that object from the heap.
boolean	isEmpty() Returns true iff the heap is empty.
Iterator<E>	iterator() Returns an iterator over its elements, in order.
E	min() Returns the minimum Object in this heap.
int	size() The number of elements currently in the heap.

Method Detail

extractMin

E extractMin()

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

Returns:

the minimum object

min

E min()

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

Returns:

the minimum object

add

boolean add(E 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

Returns:

true, always

size

int size()

The number of elements currently in the heap.

Returns:

the heap's size

isEmpty

boolean isEmpty()

Returns true iff the heap is empty.

Returns:

a boolean value

decreaseKey

int decreaseKey(E 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

iterator

Iterator<E> iterator()

Returns an iterator over its elements, in order.

Returns:

an Iterator value