edu.uci.ics.jung.utils
Class MapBinaryHeap

java.lang.Object
  edu.uci.ics.jung.utils.MapBinaryHeap

public class MapBinaryHeap

extends java.lang.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

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

MapBinaryHeap(java.util.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(java.lang.Object o)
boolean	isEmpty()
java.lang.Object	peek()
java.lang.Object	pop()
int	size() Returns the size of this heap.
void	update(java.lang.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

MapBinaryHeap

public MapBinaryHeap(java.util.Comparator c)

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

MapBinaryHeap

public MapBinaryHeap()

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()

See Also:

PriorityQueue.clear()

insert

public void insert(java.lang.Object o)

See Also:

PriorityQueue.insert(java.lang.Object)

isEmpty

public boolean isEmpty()

See Also:

PriorityQueue.isEmpty()

peek

public java.lang.Object peek()
                      throws java.util.NoSuchElementException

Throws:

java.util.NoSuchElementException

See Also:

PriorityQueue.peek()

pop

public java.lang.Object pop()
                     throws java.util.NoSuchElementException

Throws:

java.util.NoSuchElementException

See Also:

PriorityQueue.pop()

size

public int size()

Returns the size of this heap.

update

public void update(java.lang.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 -