|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object nz.ac.waikato.jdsl.core.ref.ArrayHeap
public class 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 keys
java.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
public java.lang.Object removeMin()
removeMin
in interface PriorityQueue
public Locator insert(java.lang.Object key, java.lang.Object elem)
insert
in interface KeyBasedContainer
key
- the key associated with the specified element.elem
- the element to insert into the container.
public void remove(Locator loc)
remove
in interface KeyBasedContainer
loc
- a locator in the container to removepublic java.lang.Object replaceKey(Locator loc, java.lang.Object key)
replaceKey
in interface KeyBasedContainer
loc
- the locator in the container whose key should be replacedkey
- the new key to associate with loc
.
public ObjectIterator keys()
keys
in interface InspectableKeyBasedContainer
public LocatorIterator locators()
locators
in interface InspectableKeyBasedContainer
public Container newContainer()
newContainer
in interface Container
public java.lang.Object replaceElement(Accessor a, java.lang.Object elem)
replaceElement
in interface Container
a
- Accessor in this containerelem
- to be stored at a
public boolean contains(Accessor a)
contains
in interface InspectableContainer
public ObjectIterator elements()
elements
in interface InspectableContainer
public boolean isEmpty()
isEmpty
in interface InspectableContainer
true
if and only if the container is empty (holds
no elements)InspectableBinaryTree
public int size()
size
in interface 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: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |