jdsl.core.ref
Class ArrayHeap

java.lang.Object
  jdsl.core.ref.ArrayHeap

All Implemented Interfaces:

Container, InspectableContainer, InspectableKeyBasedContainer, KeyBasedContainer, PriorityQueue, Serializable

public class ArrayHeap

extends Object

implements PriorityQueue, 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:

JDSL 2.1.1

Author:

Mark Handy (mdh), Benoit Hudson (bh), Luca Vismara (lv)

See Also:

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

defaultInitialCapacity

public static final int defaultInitialCapacity

See Also:

Constant Field Values

Constructor Detail

ArrayHeap

public ArrayHeap(Comparator comp)
          throws 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:

IllegalArgumentException - if comp is null

ArrayHeap

public ArrayHeap(Comparator comp,
                 boolean shrink)
          throws 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:

IllegalArgumentException - if comp is null

ArrayHeap

public ArrayHeap(Comparator comp,
                 int initialCapacity,
                 boolean shrink)
          throws 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:

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

Returns:

the locator to the element with highest priority in the priority queue

removeMin

public 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

Returns:

an element with highest priority in the priority queue

insert

public 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. time complexity = amortized O(log n)

Specified by:

insert in interface KeyBasedContainer

Parameters:

key - the key associated with the specified element.

elem - the element to insert into the container.

Returns:

a locator associated with the inserted pair.

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

Parameters:

loc - a locator in the container to remove

replaceKey

public Object replaceKey(Locator loc,
                         Object key)

time complexity = worst-case O(log n)

Specified by:

replaceKey in interface 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

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

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

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

Returns:

A new, empty Container of the same class as this one.

replaceElement

public Object replaceElement(Accessor a,
                             Object elem)

time complexity = worst-case O(1)

Specified by:

replaceElement in interface Container

Parameters:

a - Accessor in this container

elem - to be stored at a

Returns:

old element, previously stored at a

contains

public boolean contains(Accessor a)

time complexity = worst-case O(1)

Specified by:

contains in interface InspectableContainer

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

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

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

Returns:

Number of elements stored by the container.

toString

public String toString()

time complexity = worst-case O(n)

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