EDU.oswego.cs.dl.util.concurrent

Class 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. ]

Field Summary

protected Comparator
cmp_
protected int
count_
protected Object[]
nodes_

Constructor Summary

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

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 *

Field Details

cmp_

protected final Comparator cmp_

count_

protected int count_

nodes_

protected Object[] nodes_

Constructor Details

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

Method Details

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 *