maspack.util
Class IndexedBinaryHeap

java.lang.Object
  extended by maspack.util.IndexedBinaryHeap

public class IndexedBinaryHeap
extends java.lang.Object

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. The difference between this and BinaryHeap is that it works solely using indices. This is to speed up the update procedure.

Field Summary
static boolean DEFAULT_MIN_HEAP
           
 
Constructor Summary
IndexedBinaryHeap(int dataSize, java.util.Comparator<java.lang.Integer> indexedComparator)
          Creates a minimum BinaryHeap with given data capacity/maximum data array size
IndexedBinaryHeap(int dataSize, java.util.Comparator<java.lang.Integer> indexedComparator, boolean min)
          Creates a BinaryHeap according to the supplied parameters
 
Method Summary
 boolean add(int idx)
          Inserts data element idx into the heap
 void clear()
           
 java.util.Comparator<java.lang.Integer> comparator()
          Returns the comparator used to order elements
 boolean isEmpty()
          Returns whether or not the heap is empty
 boolean isMaxHeap()
          Returns true if this is a max-heap
 boolean isMinHeap()
          Returns true if this is a min-heap
 int peek()
          Looks at the index at the top of the heap, without removing it
 int peekLast()
          Finds the largest (or smallest) element in the heap for a min-(or max-) heap.
 int poll()
          Retrieves and removes the index of the top element in the heap
 int pollLast()
          Finds and removes largest (or smallest) element in the heap for a min-(or max-) heap.
 boolean remove(int idx)
          Removes data element at index idx from the heap
 void set(int[] valIdxs)
          Initializes a heap from an array of data indices
 void setAll()
          Initializes a heap, adding all entries
 int size()
          Number of elements in the heap
 int[] toArray()
           
<T,E> T[]
toArray(T[] a, E[] data)
           
 void update()
          Re-orders the heap.
 void update(int idx)
          Adjusts the list starting at entry number idx
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

DEFAULT_MIN_HEAP

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

IndexedBinaryHeap

public IndexedBinaryHeap(int dataSize,
                         java.util.Comparator<java.lang.Integer> indexedComparator)
Creates a minimum BinaryHeap with given data capacity/maximum data array size


IndexedBinaryHeap

public IndexedBinaryHeap(int dataSize,
                         java.util.Comparator<java.lang.Integer> indexedComparator,
                         boolean min)
Creates a BinaryHeap according to the supplied parameters

Parameters:
dataSize - the size of the indexed array, [0, dataSize-1]
indexedComparator - 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<java.lang.Integer> comparator()
Returns the comparator used to order elements


size

public int size()
Number of elements in the heap


isEmpty

public boolean isEmpty()
Returns whether or not the heap is empty


toArray

public int[] toArray()

toArray

public <T,E> T[] toArray(T[] a,
                         E[] data)

add

public boolean add(int idx)
Inserts data element idx into the heap

Parameters:
idx - index of the internal data array to add to the heap
Returns:
true if added, false if already in heap

peek

public int peek()
Looks at the index at the top of the heap, without removing it


poll

public int poll()
Retrieves and removes the index of the top element in the heap

Returns:
retrieved top element index

remove

public boolean remove(int idx)
Removes data element at index idx from the heap

Parameters:
idx - index of the element to remove
Returns:
true if element was in heap and removed, false if not in heap

peekLast

public int peekLast()
Finds the largest (or smallest) element in the heap for a min-(or max-) heap. Returns the entry's index


pollLast

public int pollLast()
Finds and removes largest (or smallest) element in the heap for a min-(or max-) heap. Returns the entry's index


clear

public void clear()

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


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(int[] valIdxs)
Initializes a heap from an array of data indices


setAll

public void setAll()
Initializes a heap, adding all entries


update

public void update(int idx)
Adjusts the list starting at entry number idx