jdsl.core.ref
Class ArrayHeap

java.lang.Object
  |
  +--jdsl.core.ref.ArrayHeap
All Implemented Interfaces:
Container, InspectableContainer, InspectableKeyBasedContainer, KeyBasedContainer, PriorityQueue, java.io.Serializable

public class ArrayHeap
extends java.lang.Object
implements PriorityQueue, java.io.Serializable

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.

Version:
$Id: ArrayHeap.java,v 1.19 2000/02/14 11:13:52 lv Exp $
Author:
Mark Handy (mdh), Benoit Hudson (bh), Luca Vismara (lv)
See Also:
Comparator, Serialized Form

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(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

defaultInitialCapacity

public static final int defaultInitialCapacity
Constructor Detail

ArrayHeap

public ArrayHeap(Comparator comp)
          throws java.lang.IllegalArgumentException
Creates a new heap. The initial capacity of the array is of defaultInitialCapacity elements. The capacity is doubled when needed, and halved when the load factor of the array is less than or equal to 0.25.
Parameters:
comp - the comparator to be used for comparing keys
Throws:
java.lang.IllegalArgumentException - if comp is null

ArrayHeap

public ArrayHeap(Comparator comp,
                 boolean shrink)
          throws java.lang.IllegalArgumentException
Creates a new heap. The initial capacity of the array is of defaultInitialCapacity elements. The capacity is doubled when needed, and possibly halved when the load factor of the array is less than or equal to 0.25.
Parameters:
comp - the comparator to be used for comparing keys
shrink - indicates whether the array should be halved when the load factor of the array is less than or equal to 0.25.
Throws:
java.lang.IllegalArgumentException - if comp is null

ArrayHeap

public ArrayHeap(Comparator comp,
                 int initialCapacity,
                 boolean shrink)
          throws java.lang.IllegalArgumentException
Creates a new heap. The capacity is doubled when needed, and possibly halved when the load factor of the array is less than or equal to 0.25.
Parameters:
comp - the comparator to be used for comparing keys
initialCapacity - the initial capacity of the array; must be a power of 2 no greater than 2^30
shrink - indicates whether the array should be halved when the load factor of the array is less than or equal to 0.25.
Throws:
java.lang.IllegalArgumentException - if comp is null or initialCapacity is greater than 2^30
Method Detail

min

public Locator min()
time complexity = worst-case O(1)
Specified by:
min in interface PriorityQueue
Following copied from interface: jdsl.core.api.PriorityQueue
Returns:
the locator to the element with highest priority in the priority queue
Throws:
EmptyContainerException - if the priority queue is empty

removeMin

public 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. time complexity = worst-case O(log n) if array-shrinking is specified at construction time, amortized O(log n) otherwise
Specified by:
removeMin in interface PriorityQueue
Following copied from interface: jdsl.core.api.PriorityQueue
Returns:
an element with highest priority in the priority queue
Throws:
EmptyContainerException - if the priority queue is empty

insert

public 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. time complexity = amortized O(log n)
Specified by:
insert in interface KeyBasedContainer
Following copied from interface: jdsl.core.api.KeyBasedContainer
Parameters:
key - the key associated with the specified element.
element - the element to insert into the container.
Returns:
a locator associated with the inserted pair.
Throws:
InvalidKeyException - if key cannot be used by this container

remove

public 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. time complexity = worst-case O(log n) if array-shrinking is specified at construction time, amortized O(log n) otherwise
Specified by:
remove in interface KeyBasedContainer
Following copied from interface: jdsl.core.api.KeyBasedContainer
Parameters:
loc - a locator in the container to remove
Throws:
InvalidAccessorException - if the locator is not valid or is not contained by this container

replaceKey

public java.lang.Object replaceKey(Locator loc,
                                   java.lang.Object key)
time complexity = worst-case O(log n)
Specified by:
replaceKey in interface KeyBasedContainer
Following copied from interface: jdsl.core.api.KeyBasedContainer
Parameters:
loc - the locator in the container whose key should be replaced
key - the new key to associate with loc.
Returns:
The old key
Throws:
InvalidAccessorException - If the locator is not valid or is not contained by this container
InvalidKeyException - If key cannot be used by this container

keys

public ObjectIterator keys()
Cached for constant factor efficiency. If the container has not been structurally modified and no key has been modified since the last time this method was invoked, there is no need to copy the elements in a new array. time complexity = worst-case O(n)
Specified by:
keys in interface InspectableKeyBasedContainer
Following copied from interface: jdsl.core.api.InspectableKeyBasedContainer
Returns:
an iterator over all the keys stored in this container

locators

public LocatorIterator locators()
Cached for constant factor efficiency. If the container has not been structurally modified since the last time this method was invoked, there is no need to copy the locators in a new array. time complexity = worst-case O(n)
Specified by:
locators in interface InspectableKeyBasedContainer
Following copied from interface: jdsl.core.api.InspectableKeyBasedContainer
Returns:
a LocatorIterator over all of the locators in the container

newContainer

public Container newContainer()
time complexity = worst-case O(1)
Specified by:
newContainer in interface Container
Following copied from interface: jdsl.core.api.Container
Returns:
A new, empty Container of the same class as this one.

replaceElement

public java.lang.Object replaceElement(Accessor a,
                                       java.lang.Object elem)
time complexity = worst-case O(1)
Specified by:
replaceElement in interface Container
Following copied from interface: jdsl.core.api.Container
Parameters:
a - Accessor in this container
newElement - to be stored at a
Returns:
old element, previously stored at a
Throws:
InvalidAccessorException - if a is null or does not belong to this container

contains

public boolean contains(Accessor a)
time complexity = worst-case O(1)
Specified by:
contains in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Throws:
InvalidAccessorException - if a is null

elements

public ObjectIterator elements()
Cached for constant factor efficiency. If the container has not been structurally modified and no element has been modified since the last time this method was invoked, there is no need to copy the elements in a new array. time complexity = worst-case O(n)
Specified by:
elements in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
an iterator over all the elements stored in this container

isEmpty

public boolean isEmpty()
time complexity = worst-case O(1)
Specified by:
isEmpty in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
true if and only if the container is empty (holds no elements)
See Also:
InspectableBinaryTree

size

public int size()
time complexity = worst-case O(1)
Specified by:
size in interface InspectableContainer
Following copied from interface: jdsl.core.api.InspectableContainer
Returns:
Number of elements stored by the container.

toString

public java.lang.String toString()
time complexity = worst-case O(n)
Overrides:
toString in class java.lang.Object

inspectableBinaryTree

public InspectableBinaryTree inspectableBinaryTree()
Creates an InspectableBinaryTree snapshot view of the heap. time complexity = worst-case O(n)
Returns:
the inspectable binary tree snapshot view
Throws:
EmptyContainerException - if the prority queue is empty