alma.ACS.jbaci

Class Heap

java.lang.Object

alma.ACS.jbaci.Heap

public class Heap
extends java.lang.Object

A heap-based priority queue. The class currently uses a standard array-based heap, as described in, for example, Sedgewick's Algorithms text. All methods are fully synchronized.

Field Summary

Fields

Modifier and Type	Field and Description
protected java.util.Comparator	cmp_ Ordering comparator.
protected int	count_ Number of used slots.
protected java.lang.Object[]	nodes_ The tree nodes, packed into an array.

Constructor Summary

Constructors

Constructor and Description
Heap(int capacity) Create a Heap with the given capacity, and relying on natural ordering.
Heap(int capacity, java.util.Comparator cmp) Create a Heap with the given initial capacity and comparator

Method Summary

Modifier and Type	Method and Description
void	clear() Remove all elements.
protected int	compare(java.lang.Object a, java.lang.Object b) Perform element comparisons using comparator or natural ordering.
java.lang.Object	extract() Return and remove least element, or null if empty.
void	insert(java.lang.Object x) Insert an element, resize if necessary.
protected int	left(int k) Get left child.
protected int	parent(int k) Get parent index.
java.lang.Object	peek() Return least element without removing it, or null if empty.
protected int	right(int k) Get right child.
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 java.lang.Object[] nodes_

The tree nodes, packed into an array.

count_

protected int count_

Number of used slots.

cmp_

protected final java.util.Comparator cmp_

Ordering comparator.

Constructor Detail

Heap

public Heap(int capacity,
            java.util.Comparator cmp)
     throws java.lang.IllegalArgumentException

Create a Heap with the given initial capacity and comparator

Parameters:

capacity - initial capacity.

cmp - comparator instance.

Throws:

java.lang.IllegalArgumentException - if capacity less or equal to zero

Heap

public Heap(int capacity)

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

Parameters:

capacity - initial capacity.

Method Detail

compare

protected int compare(java.lang.Object a,
                      java.lang.Object b)

Perform element comparisons using comparator or natural ordering.

parent

protected final int parent(int k)

Get parent index.

left

protected final int left(int k)

Get left child.

right

protected final int right(int k)

Get right child.

insert

public void insert(java.lang.Object x)

Insert an element, resize if necessary.

Parameters:

x - object to insert.

extract

public java.lang.Object extract()

Return and remove least element, or null if empty.

Returns:

extraced least element.

peek

public java.lang.Object peek()

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

Returns:

least element.

size

public int size()

Return number of elements.

Returns:

number of elements.

clear

public void clear()

Remove all elements.