maspack.util
Class BinaryHeap<E>

java.lang.Object
  extended by maspack.util.BinaryHeap<E>
Type Parameters:
E -
All Implemented Interfaces:
java.lang.Iterable<E>, java.util.Collection<E>

public class BinaryHeap<E>
extends java.lang.Object
implements java.util.Collection<E>

Author:
Antonio Implements a Balanced Binary Heap structure, much like PriorityQueue. This exposes the update function which can re-order the queue if any internal values are updated.

Nested Class Summary
static class BinaryHeap.DefaultComparator<E>
           
 
Field Summary
static int DEFAULT_CAPACITY
           
static boolean DEFAULT_MIN_HEAP
           
 
Constructor Summary
BinaryHeap()
          Creates a minimum BinaryHeap with with default initial capacity and natural ordering comparator
BinaryHeap(java.util.Comparator<E> c)
          Creates a minimum BinaryHeap that uses the supplied comparator to order values
BinaryHeap(int capacity)
          Creates a minimum BinaryHeap with with supplied initial capacity and natural ordering
BinaryHeap(int capacity, java.util.Comparator<E> c, boolean min)
          Creates a BinaryHeap according to the supplied parameters
 
Method Summary
 boolean add(E e)
          Inserts an element into the Binary Heap
 boolean addAll(java.util.Collection<? extends E> c)
           
 void clear()
           
 java.util.Comparator<E> comparator()
          Returns the comparator used to order elements
 boolean contains(java.lang.Object o)
           
 boolean containsAll(java.util.Collection<?> c)
           
 void ensureCapacity(int capacity)
          Ensures the heap's capacity is at least the supplied value
 boolean isEmpty()
           
 boolean isMaxHeap()
          Returns true if this is a max-heap
 boolean isMinHeap()
          Returns true if this is a min-heap
 java.util.Iterator<E> iterator()
           
 boolean offer(E e)
          Inserts an element into the Binary Heap
 E peek()
          Looks at the top element in the heap, without removing it
 E peekLast()
           
 E poll()
          Retrieves and removes the top element in the heap
 E pollLast()
           
 boolean remove(java.lang.Object o)
           
 boolean removeAll(java.util.Collection<?> c)
           
 boolean retainAll(java.util.Collection<?> c)
           
 void set(java.util.Collection<E> vals)
           
 void set(E[] vals)
          Initializes a heap from an array
 int size()
           
 java.lang.Object[] toArray()
           
<T> T[]
toArray(T[] a)
           
 void update()
          Re-orders the heap.
 void update(E val)
           
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 
Methods inherited from interface java.util.Collection
equals, hashCode
 

Field Detail

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY
See Also:
Constant Field Values

DEFAULT_MIN_HEAP

public static final boolean DEFAULT_MIN_HEAP
See Also:
Constant Field Values
Constructor Detail

BinaryHeap

public BinaryHeap()
Creates a minimum BinaryHeap with with default initial capacity and natural ordering comparator


BinaryHeap

public BinaryHeap(int capacity)
Creates a minimum BinaryHeap with with supplied initial capacity and natural ordering

Parameters:
capacity - initial capacity

BinaryHeap

public BinaryHeap(java.util.Comparator<E> c)
Creates a minimum BinaryHeap that uses the supplied comparator to order values


BinaryHeap

public BinaryHeap(int capacity,
                  java.util.Comparator<E> c,
                  boolean min)
Creates a BinaryHeap according to the supplied parameters

Parameters:
capacity - initial capacity
c - Comparator to use to compare elements
min - if true, creates a min-heap, otherwise creates a max-heap
Method Detail

comparator

public java.util.Comparator<E> comparator()
Returns the comparator used to order elements


size

public int size()
Specified by:
size in interface java.util.Collection<E>

isEmpty

public boolean isEmpty()
Specified by:
isEmpty in interface java.util.Collection<E>

contains

public boolean contains(java.lang.Object o)
Specified by:
contains in interface java.util.Collection<E>

iterator

public java.util.Iterator<E> iterator()
Specified by:
iterator in interface java.lang.Iterable<E>
Specified by:
iterator in interface java.util.Collection<E>

toArray

public java.lang.Object[] toArray()
Specified by:
toArray in interface java.util.Collection<E>

toArray

public <T> T[] toArray(T[] a)
Specified by:
toArray in interface java.util.Collection<E>

offer

public boolean offer(E e)
Inserts an element into the Binary Heap

Returns:
true if the element is added (always)

add

public boolean add(E e)
Inserts an element into the Binary Heap

Specified by:
add in interface java.util.Collection<E>
Returns:
true if the element is added (always)

peek

public E peek()
Looks at the top element in the heap, without removing it


poll

public E poll()
Retrieves and removes the top element in the heap


remove

public boolean remove(java.lang.Object o)
Specified by:
remove in interface java.util.Collection<E>

peekLast

public E peekLast()

pollLast

public E pollLast()

containsAll

public boolean containsAll(java.util.Collection<?> c)
Specified by:
containsAll in interface java.util.Collection<E>

addAll

public boolean addAll(java.util.Collection<? extends E> c)
Specified by:
addAll in interface java.util.Collection<E>

removeAll

public boolean removeAll(java.util.Collection<?> c)
Specified by:
removeAll in interface java.util.Collection<E>

retainAll

public boolean retainAll(java.util.Collection<?> c)
Specified by:
retainAll in interface java.util.Collection<E>

clear

public void clear()
Specified by:
clear in interface java.util.Collection<E>

isMinHeap

public boolean isMinHeap()
Returns true if this is a min-heap

Returns:
true if this is a min-heap

isMaxHeap

public boolean isMaxHeap()
Returns true if this is a max-heap


ensureCapacity

public void ensureCapacity(int capacity)
Ensures the heap's capacity is at least the supplied value


update

public void update()
Re-orders the heap. This should be called if any of the heap's priorities have changed.


set

public void set(E[] vals)
Initializes a heap from an array


set

public void set(java.util.Collection<E> vals)

update

public void update(E val)