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 Comparatorcmp_
protected intcount_
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
voidclear()
remove all elements *
protected intcompare(Object a, Object b)
perform element comaprisons using comparator or natural ordering *
Objectextract()
Return and remove least element, or null if empty
voidinsert(Object x)
insert an element, resize if necessary
protected intleft(int k)
protected intparent(int k)
Objectpeek()
Return least element without removing it, or null if empty *
protected intright(int k)
intsize()
Return number of elements *

Field Detail

cmp_

protected final Comparator cmp_

count_

protected int count_

nodes_

protected Object[] nodes_

Constructor Detail

Heap

public Heap(int capacity, Comparator cmp)
Create a Heap with the given initial capacity and comparator

Throws: 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

clear

public void clear()
remove all elements *

compare

protected int compare(Object a, Object b)
perform element comaprisons using comparator or natural ordering *

extract

public Object extract()
Return and remove least element, or null if empty

insert

public void insert(Object x)
insert an element, resize if necessary

left

protected final int left(int k)

parent

protected final int parent(int k)

peek

public Object peek()
Return least element without removing it, or null if empty *

right

protected final int right(int k)

size

public int size()
Return number of elements *