saffron.util
Class BinaryHeap

java.lang.Object
  |
  +--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

elements

private Object[] elements

comparator

private Comparator comparator

count

private int count

Constructor Detail

BinaryHeap

public BinaryHeap(boolean isMin,
                  Comparator comparator)

Method Detail

clear

public void clear()

isEmpty

public boolean isEmpty()

insert

public void insert(Object o)

percolateUp

private void percolateUp(int i)

expand

private void expand()

peek

public Object peek()
            throws NoSuchElementException

NoSuchElementException

pop

public Object pop()
           throws NoSuchElementException

NoSuchElementException

percolateDown

private void percolateDown(int i)

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

find

private int find(Object o)

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