//package opennlp.tools.util;
import java.util.Iterator;
import java.util.SortedSet;
import java.util.TreeSet;
/**
* An implementation of the Heap interface based on {@link java.util.SortedSet}.
* This implementation will not allow multiple objects which are equal to be added to the heap.
* Only use this implementation when object in the heap can be totally ordered (no duplicates).
*/
public class TreeHeap implements Heap {
private SortedSet tree;
/**
* Creates a new tree heap.
*/
public TreeHeap() {
tree = new TreeSet();
}
/**
* Creates a new tree heap of the specified size.
* @param size The size of the new tree heap.
*/
public TreeHeap(int size) {
tree = new TreeSet();
}
public Object extract() {
Object rv = tree.first();
tree.remove(rv);
return rv;
}
public Object first() {
return tree.first();
}
public Object last() {
return tree.last();
}
public Iterator iterator() {
return tree.iterator();
}
public void add(Object o) {
tree.add(o);
}
public int size() {
return tree.size();
}
public void clear() {
tree.clear();
}
public boolean isEmpty(){
return this.tree.isEmpty();
}
public static void main(String[] args) {
Heap heap = new TreeHeap(5);
for (int ai=0;ai
}
while (!heap.isEmpty()) {
System.out.print(heap.extract()+" ");
}
System.out.println();
}
}
///////////////////////////////////////////////////////////////////////////////
//Copyright (C) 2003 Thomas Morton
//
//This library is free software; you can redistribute it and/or
//modify it under the terms of the GNU Lesser General Public
//License as published by the Free Software Foundation; either
//version 2.1 of the License, or (at your option) any later version.
//
//This library is distributed in the hope that it will be useful,
//but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
//GNU Lesser General Public License for more details.
//
//You should have received a copy of the GNU Lesser General Public
//License along with this program; if not, write to the Free Software
//Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
//////////////////////////////////////////////////////////////////////////////
/** Interface for interacting with a Heap data structure.
* This implementation extract objects from smallest to largest based on either
* their natural ordering or the comparator provided to an implementation.
* While this is a typical of a heap it allows this objects natural ordering to
* match that of other sorted collections.
* */
interface Heap {
/**
* Removes the smallest element from the heap and returns it.
* @return The smallest element from the heap.
*/
public Object extract();
/**
* Returns the smallest element of the heap.
* @return The top element of the heap.
*/
public Object first();
/**
* Returns the largest element of the heap.
* @return The largest element of the heap.
*/
public Object last();
/**
* Adds the specified object to the heap.
* @param o The object to add to the heap.
*/
public void add(Object o);
/**
* Returns the size of the heap.
* @return The size of the heap.
*/
public int size();
/**
* Returns whether the heap is empty.
* @return true if the heap is empty; false otherwise.
*/
public boolean isEmpty();
/**
* Returns an iterator over the elements of the heap. No specific ordering of these
* elements is guaranteed.
* @return An iterator over the elements of the heap.
*/
public Iterator iterator();
/**
* Clears the contents of the heap.
*/
public void clear();
}