Jumpi v1.2.0

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.


Jumpi v1.2.0

Copyright 2003, Peter Jonathan Klauser.