EDU.oswego.cs.dl.util.concurrent
public class Heap extends Object
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.
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 * |
Throws: IllegalArgumentException if capacity less or equal to zero