EDU.oswego.cs.dl.util.concurrent

Class Heap

public class Heap extends 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 Comparator	cmp_
protected int	count_
protected Object[]	nodes_

Constructor Summary
	Heap(int capacity, Comparator cmp) Create a Heap with the given initial capacity and comparator
	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(Object a, Object b) perform element comaprisons using comparator or natural ordering *
Object	extract() Return and remove least element, or null if empty
void	insert(Object x) insert an element, resize if necessary
protected int	left(int k)
protected int	parent(int k)
Object	peek() Return least element without removing it, or null if empty *
protected int	right(int k)
int	size() Return number of elements *