ProGAL.dataStructures

Class Heap

java.lang.Object

ProGAL.dataStructures.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

Fields

Modifier and Type	Field and Description
protected int	count
protected java.lang.Object[]	nodes
protected SortTool	tool

Constructor Summary

Constructors

Constructor and Description
Heap(int capacity)
Heap(int capacity, SortTool tool)
Heap(Set<java.lang.Object> set, SortTool tool)

Method Summary

Modifier and Type	Method and Description
void	clear() remove all elements
java.lang.Object	extract() Return and remove least element, or null if empty
java.lang.Object	getItem(int i) returns the i-th object in the binary heap.
java.lang.Object[]	getObjects()
int	getSize()
void	insert(java.lang.Object x)
boolean	isEmpty() returns true if the heap is empty.
protected int	left(int k)
static void	main(java.lang.String[] args)
protected int	parent(int k)
java.lang.Object	peek() Return least element without removing it, or null if empty
protected int	right(int k)
void	setItem(int i, java.lang.Object x)
void	siftDown(int k)
void	siftUp(int k)
int	size() Return number of elements

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

nodes

protected java.lang.Object[] nodes

count

protected int count

tool

protected SortTool tool

Constructor Detail

Heap

public Heap(int capacity,
            SortTool tool)
     throws java.lang.IllegalArgumentException

Throws:

java.lang.IllegalArgumentException

Heap

public Heap(int capacity)

Heap

public Heap(Set<java.lang.Object> set,
            SortTool tool)

Method Detail

parent

protected final int parent(int k)

left

protected final int left(int k)

right

protected final int right(int k)

getObjects

public java.lang.Object[] getObjects()

isEmpty

public boolean isEmpty()

returns true if the heap is empty.

Returns:

getSize

public int getSize()

getItem

public java.lang.Object getItem(int i)

returns the i-th object in the binary heap. This is not a standard operation

Parameters:

i -

Returns:

setItem

public void setItem(int i,
                    java.lang.Object x)

siftUp

public void siftUp(int k)

siftDown

public void siftDown(int k)

insert

public void insert(java.lang.Object x)

extract

public java.lang.Object extract()

Return and remove least element, or null if empty

peek

public java.lang.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

main

public static void main(java.lang.String[] args)

Parameters:

args -