EDU.oswego.cs.dl.util.concurrent
Class Heap

java.lang.Object
  EDU.oswego.cs.dl.util.concurrent.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 java.util.Comparator	cmp_
protected int	count_
protected java.lang.Object[]	nodes_

Constructor Summary

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

void	clear() remove all elements
protected int	compare(java.lang.Object a, java.lang.Object b) perform element comaprisons 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)
protected int	parent(int k)
java.lang.Object	peek() Return least element without removing it, or null if empty
protected int	right(int k)
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_

count_

protected int count_

cmp_

protected final java.util.Comparator cmp_

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

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.

Method Detail

compare

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

perform element comaprisons using comparator or natural ordering

parent

protected final int parent(int k)

left

protected final int left(int k)

right

protected final int right(int k)

insert

public void insert(java.lang.Object x)

insert an element, resize if necessary

extract

public java.lang.Object extract()

Return and remove least element, or null if empty

peek

public java.lang.Object peek()

Return least element without removing it, or null if empty

size

public int size()

Return number of elements

clear

public void clear()

remove all elements