EDU.oswego.cs.dl.util.concurrent
public class Heap extends java.lang.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.
Modifier and Type | Field and Description |
---|---|
protected java.util.Comparator |
cmp_ |
protected int |
count_ |
protected java.lang.Object[] |
nodes_ |
Constructor and Description |
---|
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
|
Modifier and Type | Method and Description |
---|---|
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
|
protected java.lang.Object[] nodes_
protected int count_
protected final java.util.Comparator cmp_
public Heap(int capacity, java.util.Comparator cmp) throws java.lang.IllegalArgumentException
java.lang.IllegalArgumentException
- if capacity less or equal to zeropublic Heap(int capacity)
protected int compare(java.lang.Object a, java.lang.Object b)
protected final int parent(int k)
protected final int left(int k)
protected final int right(int k)
public void insert(java.lang.Object x)
public java.lang.Object extract()
public java.lang.Object peek()
public int size()
public void clear()