com.aliasi.util
Class MinMaxHeap<E extends Scored>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by com.aliasi.util.MinMaxHeap<E>
Type Parameters:
E - the type of objects stored in the heap
All Implemented Interfaces:
Iterable<E>, Collection<E>

public class MinMaxHeap<E extends Scored>
extends AbstractCollection<E>

A MinMaxHeap provides a heap-like data structure that provides fast access to both the minimum and maximum elements of the heap. Each min-max heap is of a fixed maximum size. A min-max heap holds elements implementing the Scored interface, with scores being used for sorting.

A min-max heap data structure is useful to implement priority queues with fixed numbers of elements, which requires access to both the best and worst elements of the queue.

This implementation is based on the paper:

Since:
LingPipe2.4.0
Version:
3.8
Author:
Bob Carpenter

Constructor Summary
MinMaxHeap(int maxSize)
          Construct a min-max heap holding up to the specified number of elements.
 
Method Summary
 boolean add(E s)
          Add the element to the heap.
 Iterator<E> iterator()
          Returns an iterator over this heap.
 E peekMax()
          Returns the maximum element in the heap, or null if it is empty.
 E peekMin()
          Returns the minimum element in the heap, or null if it is empty.
 E popMax()
          Returns the maximum element in the heap after removing it, or returns null if the heap is empty.
 E popMin()
          Returns the minimum element in the heap after removing it, or returns null if the heap is empty.
 int size()
          Returns the current size of this heap.
 String toString()
          Returns a string-based representation of this heap.
 
Methods inherited from class java.util.AbstractCollection
addAll, clear, contains, containsAll, isEmpty, remove, removeAll, retainAll, toArray, toArray
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Constructor Detail

MinMaxHeap

public MinMaxHeap(int maxSize)
Construct a min-max heap holding up to the specified number of elements. Min-max heaps do not grow dynamically and attempts to push an element onto a full heap will result in exceptions.

Parameters:
maxSize - Maximum number of elements in the heap.
Method Detail

size

public int size()
Returns the current size of this heap.

Specified by:
size in interface Collection<E extends Scored>
Specified by:
size in class AbstractCollection<E extends Scored>
Returns:
The size of the heap.

iterator

public Iterator<E> iterator()
Returns an iterator over this heap. The elements are returned in decreasing order of score.

Specified by:
iterator in interface Iterable<E extends Scored>
Specified by:
iterator in interface Collection<E extends Scored>
Specified by:
iterator in class AbstractCollection<E extends Scored>
Returns:
Iterator over this heap in decreasing order of score.

add

public boolean add(E s)
Add the element to the heap.

Specified by:
add in interface Collection<E extends Scored>
Overrides:
add in class AbstractCollection<E extends Scored>
Parameters:
s - Element to add to heap.
Returns:
true if the element is added.

peekMax

public E peekMax()
Returns the maximum element in the heap, or null if it is empty.

Returns:
The largest element in the heap.

peekMin

public E peekMin()
Returns the minimum element in the heap, or null if it is empty.

Returns:
The smallest element in the heap.

popMax

public E popMax()
Returns the maximum element in the heap after removing it, or returns null if the heap is empty.

Returns:
The largest element in the heap.

popMin

public E popMin()
Returns the minimum element in the heap after removing it, or returns null if the heap is empty.

Returns:
The smallest element in the heap.

toString

public String toString()
Returns a string-based representation of this heap.

Overrides:
toString in class AbstractCollection<E extends Scored>
Returns:
String representation of this heap.