edu.stanford.nlp.util
Class ArrayHeap<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<E>
          edu.stanford.nlp.util.ArrayHeap<E>

All Implemented Interfaces:

Heap<E>, Iterable<E>, Collection<E>, Set<E>

public class ArrayHeap<E>
extends AbstractSet<E>
implements Heap<E>

Implements a heap as an ArrayList. 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.

Author:

Dan Klein, Christopher Manning

Constructor Summary

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

ArrayHeap(Comparator cmp, int initCapacity)

Method Summary

boolean	add(E o) Adds an object to the heap.
void	clear() Clears the heap.
int	decreaseKey(E o) Changes the position of an element o in the heap based on a change in the ordering of o.
void	dump()
E	extractMin() Finds the object with the minimum key, removes it from the heap, and returns it.
boolean	isEmpty() Checks if the heap is empty.
Iterator<E>	iterator() Returns an iterator over its elements, in order.
E	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.
String	toString() Prints the array entries in sorted comparator order.
void	verify()

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, contains, containsAll, remove, retainAll, toArray, toArray

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, contains, containsAll, remove, retainAll, toArray, toArray

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 E extractMin()

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

Specified by:

extractMin in interface Heap<E>

Returns:

the object with minimum key

min

public E min()

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

Specified by:

min in interface Heap<E>

Returns:

the object with minimum key

add

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

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

Overrides:

add in class AbstractCollection<E>

Parameters:

o - an Object value

Returns:

true, always

decreaseKey

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

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<E>

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface Set<E>

Overrides:

isEmpty in class AbstractCollection<E>

Returns:

a boolean value

size

public int size()

Get the number of elements in the heap.

Specified by:

size in interface Heap<E>

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

Specified by:

size in class AbstractCollection<E>

Returns:

an int value

iterator

public Iterator<E> iterator()

Description copied from interface: Heap

Returns an iterator over its elements, in order.

Specified by:

iterator in interface Heap<E>

Specified by:

iterator in interface Iterable<E>

Specified by:

iterator in interface Collection<E>

Specified by:

iterator in interface Set<E>

Specified by:

iterator in class AbstractCollection<E>

Returns:

an Iterator value

clear

public void clear()

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

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

Overrides:

clear in class AbstractCollection<E>

dump

public void dump()

verify

public void verify()

toString

public String toString()

Prints the array entries in sorted comparator order.

Overrides:

toString in class AbstractCollection<E>

Returns: