|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--jdsl.core.ref.ArrayHeap
An array implementation of a heap.
The number of elements that can be stored in the array or in the heap is called capacity. The capacity of the heap is always the capacity of the array minus one. The initial capacity of the array is the public constant defaultInitialCapacity (or the capacity specified in the constructor); the maximum capacity of the array is 2^30. The capacity of the array is doubled when needed. The load factor of the array is the ratio of the number of elements stored in the array to the capacity of the array. If array-shrinking is specified at construction time, the capacity of the array is halved when the load factor of the array is less than or equal to 0.25.
A binary heap such as this one has O(log n) insert, remove, and replaceKey, and O(1) min.
Internal ordering is maintained according to the order of the given
Comparator. Of the Comparator methods, only
compare(.)
is used.
Comparator
, Serialized FormField Summary | |
static int |
defaultInitialCapacity
|
Constructor Summary | |
ArrayHeap(Comparator comp)
Creates a new heap. |
|
ArrayHeap(Comparator comp,
boolean shrink)
Creates a new heap. |
|
ArrayHeap(Comparator comp,
int initialCapacity,
boolean shrink)
Creates a new heap. |
Method Summary | |
boolean |
contains(Accessor a)
time complexity = worst-case O(1) |
ObjectIterator |
elements()
Cached for constant factor efficiency. |
Locator |
insert(java.lang.Object key,
java.lang.Object elem)
If the array is full, its capacity is doubled before the insertion by copying the elements into a new array. |
InspectableBinaryTree |
inspectableBinaryTree()
Creates an InspectableBinaryTree snapshot view of the heap. |
boolean |
isEmpty()
time complexity = worst-case O(1) |
ObjectIterator |
keys()
Cached for constant factor efficiency. |
LocatorIterator |
locators()
Cached for constant factor efficiency. |
Locator |
min()
time complexity = worst-case O(1) |
Container |
newContainer()
time complexity = worst-case O(1) |
void |
remove(Locator loc)
If array-shrinking is specified at construction time and the load factor of the array is 0.25 after the removal, the capacity of the array is halved by copying the elements into a new array. |
java.lang.Object |
removeMin()
If array-shrinking is specified at construction time and the load factor of the array is 0.25 after the removal, the capacity of the array is halved by copying the elements into a new array. |
java.lang.Object |
replaceElement(Accessor a,
java.lang.Object elem)
time complexity = worst-case O(1) |
java.lang.Object |
replaceKey(Locator loc,
java.lang.Object key)
time complexity = worst-case O(log n) |
int |
size()
time complexity = worst-case O(1) |
java.lang.String |
toString()
time complexity = worst-case O(n) |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Field Detail |
public static final int defaultInitialCapacity
Constructor Detail |
public ArrayHeap(Comparator comp) throws java.lang.IllegalArgumentException
comp
- the comparator to be used for comparing keysjava.lang.IllegalArgumentException
- if comp is nullpublic ArrayHeap(Comparator comp, boolean shrink) throws java.lang.IllegalArgumentException
comp
- the comparator to be used for comparing keysshrink
- indicates whether the array should be halved when
the load factor of the array is less than or equal to 0.25.java.lang.IllegalArgumentException
- if comp is nullpublic ArrayHeap(Comparator comp, int initialCapacity, boolean shrink) throws java.lang.IllegalArgumentException
comp
- the comparator to be used for comparing keysinitialCapacity
- the initial capacity of the array; must be
a power of 2 no greater than 2^30shrink
- indicates whether the array should be halved when
the load factor of the array is less than or equal to 0.25.java.lang.IllegalArgumentException
- if comp is null or
initialCapacity is greater than 2^30Method Detail |
public Locator min()
min
in interface PriorityQueue
jdsl.core.api.PriorityQueue
EmptyContainerException
- if the priority queue is emptypublic java.lang.Object removeMin()
removeMin
in interface PriorityQueue
jdsl.core.api.PriorityQueue
EmptyContainerException
- if the priority queue is emptypublic Locator insert(java.lang.Object key, java.lang.Object elem)
insert
in interface KeyBasedContainer
jdsl.core.api.KeyBasedContainer
key
- the key associated with the specified element.element
- the element to insert into the container.InvalidKeyException
- if key
cannot be used
by this containerpublic void remove(Locator loc)
remove
in interface KeyBasedContainer
jdsl.core.api.KeyBasedContainer
loc
- a locator in the container to removeInvalidAccessorException
- if the locator is not valid or
is not contained by this containerpublic java.lang.Object replaceKey(Locator loc, java.lang.Object key)
replaceKey
in interface KeyBasedContainer
jdsl.core.api.KeyBasedContainer
loc
- the locator in the container whose key should be replacedkey
- the new key to associate with loc
.InvalidAccessorException
- If the locator is not valid
or is not contained by this containerInvalidKeyException
- If key
cannot be used
by this containerpublic ObjectIterator keys()
keys
in interface InspectableKeyBasedContainer
jdsl.core.api.InspectableKeyBasedContainer
public LocatorIterator locators()
locators
in interface InspectableKeyBasedContainer
jdsl.core.api.InspectableKeyBasedContainer
public Container newContainer()
newContainer
in interface Container
jdsl.core.api.Container
public java.lang.Object replaceElement(Accessor a, java.lang.Object elem)
replaceElement
in interface Container
jdsl.core.api.Container
a
- Accessor in this containernewElement
- to be stored at aInvalidAccessorException
- if a is null or does not
belong to this containerpublic boolean contains(Accessor a)
contains
in interface InspectableContainer
jdsl.core.api.InspectableContainer
InvalidAccessorException
- if a is nullpublic ObjectIterator elements()
elements
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public boolean isEmpty()
isEmpty
in interface InspectableContainer
jdsl.core.api.InspectableContainer
true
if and only if the container is empty (holds
no elements)InspectableBinaryTree
public int size()
size
in interface InspectableContainer
jdsl.core.api.InspectableContainer
public java.lang.String toString()
toString
in class java.lang.Object
public InspectableBinaryTree inspectableBinaryTree()
EmptyContainerException
- if the prority queue is empty
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |