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

Constructor Summary

Heap(int capacity)

Heap(int capacity, SortTool tool)

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

Method Summary

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.
static void	main(java.lang.String[] args)
java.lang.Object	peek() Return least element without removing it, or null if empty
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

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

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

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 -