Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.uci.ics.jung.utils
Class MapBinaryHeap

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

All Implemented Interfaces:
  Collection

public class MapBinaryHeap
extends AbstractCollection
implements Collection

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.

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(Collection 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(Collection c, Comparator comp)` Creates a `MapBinaryHeap` based on the specified collection whose heap ordering is based on the ordering of the elements specified by `c`.
`MapBinaryHeap(Comparator comp)` Creates a `MapBinaryHeap` whose heap ordering is based on the ordering of the elements specified by `c`.

Method Summary
`boolean` | `add(Object o)` Inserts `o` into this collection.
`void` | `clear()`
`boolean` | `contains(Object o)`
`boolean` | `isEmpty()` Returns `true` if this collection contains no elements, and `false` otherwise.
`Iterator` | `iterator()` Returns an `Iterator` that does not support modification of the heap.
`Object` | `peek()` Returns the element at the top of the heap; does not alter the heap.
`Object` | `pop()` Removes the element at the top of this heap, and returns it.
`boolean` | `remove(Object o)` This data structure does not support the removal of arbitrary elements.
`boolean` | `removeAll(Collection c)` This data structure does not support the removal of arbitrary elements.
`boolean` | `retainAll(Collection c)` This data structure does not support the removal of arbitrary elements.
`int` | `size()` Returns the size of this heap.
`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.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, toArray, toArray`

Constructor Detail

### MapBinaryHeap

    public MapBinaryHeap(Comparator 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(Collection 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(Collection c,
                         Comparator 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 `Collection`
  See Also:
    `Collection.clear()`

### add

    public boolean add(Object o)

  Inserts `o` into this collection.

  Specified by:
    `add` in interface `Collection`

### isEmpty

    public boolean isEmpty()

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

  Specified by:
    `isEmpty` in interface `Collection`

### peek

    public Object peek()
                throws NoSuchElementException

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

  Throws:
    `NoSuchElementException`

### pop

    public Object pop()
               throws NoSuchElementException

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

  Throws:
    `NoSuchElementException`

### size

    public int size()

  Returns the size of this heap.

  Specified by:
    `size` in interface `Collection`

### 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` -

### contains

    public boolean contains(Object o)

  Specified by:
    `contains` in interface `Collection`
  See Also:
    `Collection.contains(java.lang.Object)`

### iterator

    public Iterator iterator()

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

  Specified by:
    `iterator` in interface `Collection`

### remove

    public boolean remove(Object o)

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

  Specified by:
    `remove` in interface `Collection`

### removeAll

    public boolean removeAll(Collection c)

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

  Specified by:
    `removeAll` in interface `Collection`

### retainAll

    public boolean retainAll(Collection c)

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

  Specified by:
    `retainAll` in interface `Collection`

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD