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. ]
Heap(int capacity) - Create a Heap with the given capacity,
and relying on natural ordering.
|
Heap(int capacity, Comparator cmp) - Create a Heap with the given initial capacity and comparator
|
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 *
|
cmp_
protected final Comparator cmp_
count_
protected int count_
nodes_
protected Object[] nodes_
Heap
public Heap(int capacity)
Create a Heap with the given capacity,
and relying on natural ordering.
Heap
public Heap(int capacity,
Comparator cmp)
throws IllegalArgumentException
Create a Heap with the given initial capacity and comparator
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 *