org.jumpi.impl.util
Class Heap

java.lang.Object
  |
  +--org.jumpi.impl.util.Heap

public class Heap

extends java.lang.Object

A heap-based priority queue, without any concurrency control (i.e., no blocking on empty/full states). This class provides the data structure mechanics for BoundedPriorityQueue.

The class currently uses a standard array-based heap, as described in, for example, Sedgewick's Algorithms text. All methods are fully synchronized. In the future, it may instead use structures permitting finer-grained locking.

[ Introduction to this package. ]

Field Summary

protected int	capacity_ Initial capacity.
protected int	count_ Number of used slots.
protected Comparable[]	nodes_ The tree nodes, packed into an array.

Constructor Summary

Heap(int capacity)
Create a Heap with the given capacity, and relying on natural ordering.

Method Summary

void	clear() Remove all elements.
protected int	compare(Comparable a, Comparable b) Perform element comparisons using comparator or natural ordering.
Comparable	extract() Return and remove least element, or null if empty.
void	insert(Comparable x) Insert an element, resize if necessary.
protected int	left(int k) Return the index of the left child of a parent with the given index.
protected int	parent(int k) Return the index in the heap of the parent of node at the given index.
Comparable	peek() Return least element without removing it, or null if empty.
protected int	right(int k) Return the index of the right child of a parent with the given index.
int	size() Return number of elements.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

nodes_

protected Comparable[] nodes_

The tree nodes, packed into an array.

count_

protected int count_

Number of used slots.

capacity_

protected int capacity_

Initial capacity.

Constructor Detail

Heap

public Heap(int capacity)

Create a Heap with the given capacity, and relying on natural ordering.

Parameters:

capacity - the initial capacity.

Throws:

java.lang.IllegalArgumentException - when capacity smaller than or equal to zero.

Method Detail

compare

protected int compare(Comparable a,
                      Comparable b)

Perform element comparisons using comparator or natural ordering.

Parameters:

a - first object.

b - second object.

Returns:

comparison of the first with the second object.

parent

protected final int parent(int k)

Return the index in the heap of the parent of node at the given index.

Parameters:

k - the child's index.

Returns:

the index of the parent.

left

protected final int left(int k)

Return the index of the left child of a parent with the given index.

Parameters:

k - the parent's index.

Returns:

the index of the left child.

right

protected final int right(int k)

Return the index of the right child of a parent with the given index.

Parameters:

k - the parent's index.

Returns:

the index of the right child.

insert

public void insert(Comparable x)

Insert an element, resize if necessary. Will be inserted according to the ordering with the other nodes already in the tree. A parent node must always be comparably less than its children. Never blocks.

Parameters:

x - the object to insert.

Throws:

java.lang.IllegalArgumentException - when x is null.

extract

public Comparable extract()

Return and remove least element, or null if empty. Never blocks.

Returns:

the least element in the heap, or null if empty.

peek

public Comparable peek()

Return least element without removing it, or null if empty. Never blocks.

Returns:

the least element, or null if empty.

size

public int size()

Return number of elements.

Returns:

the number of elements.

clear

public void clear()

Remove all elements.