|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjdsl.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
Field 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(Object key,
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. |
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. |
Object |
replaceElement(Accessor a,
Object elem)
time complexity = worst-case O(1) |
Object |
replaceKey(Locator loc,
Object key)
time complexity = worst-case O(log n) |
int |
size()
time complexity = worst-case O(1) |
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 IllegalArgumentException
comp
- the comparator to be used for comparing keys
IllegalArgumentException
- if comp is nullpublic ArrayHeap(Comparator comp, boolean shrink) throws 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.
IllegalArgumentException
- if comp is nullpublic ArrayHeap(Comparator comp, int initialCapacity, boolean shrink) throws 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.
IllegalArgumentException
- if comp is null or
initialCapacity is greater than 2^30Method Detail |
public Locator min()
min
in interface PriorityQueue
public Object removeMin()
removeMin
in interface PriorityQueue
public Locator insert(Object key, 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 Object replaceKey(Locator loc, 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 Object replaceElement(Accessor a, 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 String toString()
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 |