edu.uci.ics.jung.algorithms.util

Class MapBinaryHeap<T>

java.lang.Object

java.util.AbstractCollection<T>

edu.uci.ics.jung.algorithms.util.MapBinaryHeap<T>

All Implemented Interfaces:

java.lang.Iterable<T>, java.util.Collection<T>, java.util.Queue<T>

public class MapBinaryHeap<T>
extends java.util.AbstractCollection<T>
implements java.util.Queue<T>

An array-based binary heap implementation of a priority queue, which also provides efficient update() and contains operations. 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.

Constructor Summary

Constructors

Constructor and Description
MapBinaryHeap() Creates a MapBinaryHeap whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
MapBinaryHeap(java.util.Collection<T> c) Creates a MapBinaryHeap based on the specified collection whose heap ordering will be based on the natural ordering of the elements, which must be Comparable.
MapBinaryHeap(java.util.Collection<T> c, java.util.Comparator<T> comp) Creates a MapBinaryHeap based on the specified collection whose heap ordering is based on the ordering of the elements specified by c.
MapBinaryHeap(java.util.Comparator<T> comp) Creates a MapBinaryHeap whose heap ordering is based on the ordering of the elements specified by c.

Method Summary

Modifier and Type	Method and Description
boolean	add(T o) Inserts o into this collection.
void	clear()
boolean	contains(java.lang.Object o)
T	element()
boolean	isEmpty() Returns true if this collection contains no elements, and false otherwise.
java.util.Iterator<T>	iterator() Returns an Iterator that does not support modification of the heap.
boolean	offer(T o)
T	peek() Returns the element at the top of the heap; does not alter the heap.
T	poll()
T	pop() Deprecated. Use poll() or remove() instead.
T	remove()
boolean	remove(java.lang.Object o) This data structure does not support the removal of arbitrary elements.
boolean	removeAll(java.util.Collection<?> c) This data structure does not support the removal of arbitrary elements.
boolean	retainAll(java.util.Collection<?> c) This data structure does not support the removal of arbitrary elements.
int	size() Returns the size of this heap.
void	update(T 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.util.AbstractCollection

addAll, containsAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.util.Collection

addAll, containsAll, equals, hashCode, parallelStream, removeIf, spliterator, stream, toArray, toArray

Methods inherited from interface java.lang.Iterable

forEach

Constructor Detail

MapBinaryHeap

public MapBinaryHeap(java.util.Comparator<T> comp)

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.

MapBinaryHeap

public MapBinaryHeap(java.util.Collection<T> c)

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

MapBinaryHeap

public MapBinaryHeap(java.util.Collection<T> c,
                     java.util.Comparator<T> comp)

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

Method Detail

clear

public void clear()

Specified by:

clear in interface java.util.Collection<T>

Overrides:

clear in class java.util.AbstractCollection<T>

See Also:

Collection.clear()

add

public boolean add(T o)

Inserts o into this collection.

Specified by:

add in interface java.util.Collection<T>

Specified by:

add in interface java.util.Queue<T>

Overrides:

add in class java.util.AbstractCollection<T>

isEmpty

public boolean isEmpty()

Returns true if this collection contains no elements, and false otherwise.

Specified by:

isEmpty in interface java.util.Collection<T>

Overrides:

isEmpty in class java.util.AbstractCollection<T>

peek

public T peek()

Returns the element at the top of the heap; does not alter the heap.

Specified by:

peek in interface java.util.Queue<T>

pop

@Deprecated
public T pop()
                   throws java.util.NoSuchElementException

Deprecated. Use poll() or remove() instead.

Removes the element at the top of this heap, and returns it.

Throws:

java.util.NoSuchElementException

size

public int size()

Returns the size of this heap.

Specified by:

size in interface java.util.Collection<T>

Specified by:

size in class java.util.AbstractCollection<T>

update

public void update(T 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 -

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface java.util.Collection<T>

Overrides:

contains in class java.util.AbstractCollection<T>

See Also:

Collection.contains(java.lang.Object)

iterator

public java.util.Iterator<T> iterator()

Returns an Iterator that does not support modification of the heap.

Specified by:

iterator in interface java.lang.Iterable<T>

Specified by:

iterator in interface java.util.Collection<T>

Specified by:

iterator in class java.util.AbstractCollection<T>

remove

public boolean remove(java.lang.Object o)

This data structure does not support the removal of arbitrary elements.

Specified by:

remove in interface java.util.Collection<T>

Overrides:

remove in class java.util.AbstractCollection<T>

removeAll

public boolean removeAll(java.util.Collection<?> c)

This data structure does not support the removal of arbitrary elements.

Specified by:

removeAll in interface java.util.Collection<T>

Overrides:

removeAll in class java.util.AbstractCollection<T>

retainAll

public boolean retainAll(java.util.Collection<?> c)

This data structure does not support the removal of arbitrary elements.

Specified by:

retainAll in interface java.util.Collection<T>

Overrides:

retainAll in class java.util.AbstractCollection<T>

element

public T element()
          throws java.util.NoSuchElementException

Specified by:

element in interface java.util.Queue<T>

Throws:

java.util.NoSuchElementException

offer

public boolean offer(T o)

Specified by:

offer in interface java.util.Queue<T>

poll

public T poll()

Specified by:

poll in interface java.util.Queue<T>

remove

public T remove()

Specified by:

remove in interface java.util.Queue<T>