net.sf.saffron.util
Class BinaryHeap

java.lang.Object
  |
  +--net.sf.saffron.util.BinaryHeap

public class BinaryHeap

extends Object

A BinaryHeap is a heap implementation of a priority queue. It is similar to BinaryHeap in apache commons, but it also has a remove(java.lang.Object) method.

Since:

Dec 8, 2002

Version:

$Id $

Author:

jhyde

Nested Class Summary

static class

BinaryHeap.BinaryHeapTestCase

Field Summary

private Comparator	comparator
private int	count
private Object[]	elements

Constructor Summary

BinaryHeap(boolean isMin, Comparator comparator)

Method Summary

void	clear()
private void	expand()
private int	find(Object o) Returns the first position of an object on the heap, or 0 if not found.
void	insert(Object o)
boolean	isEmpty()
Object	peek()
private void	percolateDown(int i)
private void	percolateUp(int i)
Object	pop()
boolean	remove(Object o) Removes an object from the queue.

Methods inherited from class java.lang.Object

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

Field Detail

comparator

private Comparator comparator

elements

private Object[] elements

count

private int count

Constructor Detail

BinaryHeap

public BinaryHeap(boolean isMin,
                  Comparator comparator)

Method Detail

isEmpty

public boolean isEmpty()

clear

public void clear()

insert

public void insert(Object o)

peek

public Object peek()
            throws NoSuchElementException

NoSuchElementException

pop

public Object pop()
           throws NoSuchElementException

NoSuchElementException

remove

public boolean remove(Object o)

Removes an object from the queue. If it exists several times, removes only one occurrence.

Parameters:

o - the object to remove

Returns:

whether the object was on the queue

expand

private void expand()

find

private int find(Object o)

Returns the first position of an object on the heap, or 0 if not found.

percolateDown

private void percolateDown(int i)

percolateUp

private void percolateUp(int i)