infovis.utils
Class Heap

java.lang.Object
  infovis.utils.Heap

public class Heap
extends Object

An array-based binary heap implementation of a priority queue, which also provides an efficient update() operation. (A previous version of this class had implemented the commons-collections PriorityQueue interface, which has since been deprecated.) It contains extra infrastructure (a hash table) to keep track of the position of each element in the array; thus, if the key value of an element changes, it may be "resubmitted" to the heap via update so that the heap can reposition it efficiently, as necessary.

Author:

Joshua O'Madadhain

Constructor Summary

Heap()
Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.

Heap(Comparator c)
Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.

Method Summary

void	clear()
void	insert(Object o)
boolean	isEmpty()
Object	peek()
Object	pop()
int	size()
void	update(Object o) Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).

Methods inherited from class java.lang.Object

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

Constructor Detail

Heap

public Heap(Comparator c)

Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.

Heap

public Heap()

Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.

Method Detail

clear

public void clear()

insert

public void insert(Object o)

isEmpty

public boolean isEmpty()

peek

public Object peek()
            throws NoSuchElementException

Throws:

NoSuchElementException

pop

public Object pop()
           throws NoSuchElementException

Throws:

NoSuchElementException

size

public int size()

update

public void update(Object o)

Informs the heap that this object's internal key value has been updated, and that its place in the heap may need to be shifted (up or down).

Parameters:

o -