edu.stanford.nlp.util
Class ArrayHeap

java.lang.Object
  |
  +--edu.stanford.nlp.util.ArrayHeap

All Implemented Interfaces:

Heap

public final class ArrayHeap

extends Object

implements Heap

ArrayHeap: Heap implementation. Values are all implicit in the comparator passed in on construction. Decrease key is supported, though only lg(n). Unlike the previous implementation of this class, this heap interprets the addition of an existing element as a "change key" which gets ignored unless it actually turns out to be a decrease key. Note that in this implementation, changing the key of an object should trigger a change in the comparator's ordering for that object, but should NOT change the equality of that object.

Constructor Summary

ArrayHeap(Comparator cmp)
The objects added will be ordered using the Comparator.

ArrayHeap(Comparator cmp, int initCapacity)

Method Summary

void	add(Object o) Adds an object to the heap.
void	clear() Clears the heap.
int	decreaseKey(Object o) Changes the position of an element o in the heap based on a change in the ordering of o.
void	dump()
Object	extractMin() Finds the object with the minimum key, removes it from the heap, and returns it.
boolean	isEmpty() Checks if the heap is empty.
Object	min() Finds the object with the minimum key and returns it, without modifying the heap.
int	size() Get the number of elements in the heap.
void	verify()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ArrayHeap

public ArrayHeap(Comparator cmp)

The objects added will be ordered using the Comparator.

ArrayHeap

public ArrayHeap(Comparator cmp,
                 int initCapacity)

Method Detail

extractMin

public Object extractMin()

Finds the object with the minimum key, removes it from the heap, and returns it.

Specified by:

extractMin in interface Heap

Returns:

the object with minimum key

min

public Object min()

Finds the object with the minimum key and returns it, without modifying the heap.

Specified by:

min in interface Heap

Returns:

the object with minimum key

add

public void add(Object o)

Adds an object to the heap. If the object is already in the heap with worse score, this acts as a decrease key. If the object is already present, with better score, it will NOT cause an "increase key".

Specified by:

add in interface Heap

Parameters:

o - an Object value

decreaseKey

public int decreaseKey(Object o)

Changes the position of an element o in the heap based on a change in the ordering of o. If o's key has actually increased, it will do nothing, particularly not an "increase key".

Specified by:

decreaseKey in interface Heap

Parameters:

o - an Object value

Returns:

the number of swaps done on decrease.

isEmpty

public boolean isEmpty()

Checks if the heap is empty.

Specified by:

isEmpty in interface Heap

Returns:

a boolean value

size

public int size()

Get the number of elements in the heap.

Specified by:

size in interface Heap

Returns:

an int value

clear

public void clear()

Clears the heap. Equivalent to calling extractMin repeatedly (but faster).

dump

public void dump()

verify

public void verify()