Package EDU.oswego.cs.dl.util.concurrent
Class Heap
- java.lang.Object
-
- EDU.oswego.cs.dl.util.concurrent.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.
-
-
Field Summary
Fields Modifier and Type Field Description protected Comparator
cmp_
protected int
count_
protected Object[]
nodes_
-
Constructor Summary
Constructors Constructor Description 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
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description void
clear()
remove all elementsprotected int
compare(Object a, Object b)
perform element comaprisons using comparator or natural orderingObject
extract()
Return and remove least element, or null if emptyvoid
insert(Object x)
insert an element, resize if necessaryprotected int
left(int k)
protected int
parent(int k)
Object
peek()
Return least element without removing it, or null if emptyprotected int
right(int k)
int
size()
Return number of elements
-
-
-
Field Detail
-
nodes_
protected Object[] nodes_
-
count_
protected int count_
-
cmp_
protected final Comparator cmp_
-
-
Constructor Detail
-
Heap
public Heap(int capacity, Comparator cmp) throws IllegalArgumentException
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
-
compare
protected int compare(Object a, Object b)
perform element comaprisons using comparator or natural ordering
-
parent
protected final int parent(int k)
-
left
protected final int left(int k)
-
right
protected final int right(int k)
-
insert
public void insert(Object x)
insert an element, resize if necessary
-
extract
public Object extract()
Return and remove least element, or null if empty
-
peek
public Object peek()
Return least element without removing it, or null if empty
-
size
public int size()
Return number of elements
-
clear
public void clear()
remove all elements
-
-