brutil
Class BinaryHeap

java.lang.Object
  |
  +--brutil.BinaryHeap

All Implemented Interfaces:

Collection, PriorityQueue

public class BinaryHeap

extends java.lang.Object

implements PriorityQueue

Inner Class Summary

protected class

BinaryHeap.Element

Field Summary

protected Array	heap
static int	MAX
static int	MIN

Constructor Summary

BinaryHeap(int size, int type)

Method Summary

void	clear() Clears out the contents of the Collection (optional operation)
protected BinaryHeap.Element	createElement(java.lang.Comparable key, Handle handle, java.lang.Object data)
protected Handle	createHandle(int index)
java.lang.Object	extractFirst() Get the element with greatest priority out of the queue
java.lang.Object	getData(Handle handle)
java.lang.Comparable	getFirstKey() Get the key of the object with greatest priority.
java.lang.Object	getKey(Handle handle)
int	getType()
protected void	initMemory(int arraySize)
Handle	insert(java.lang.Comparable key, java.lang.Object data) Places the specified element into the heap and arranges it based on the value of key.
boolean	isEmpty() Returns true if the Collection contains no elements, false otherwise
int	size() Returns the size of the given Collection.
java.lang.String	toString()
boolean	updateKey(Handle handle, java.lang.Comparable newKey) Changes the key of the entry with the specified handle to the newKey.

Methods inherited from class java.lang.Object

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

Field Detail

MAX

public static final int MAX

MIN

public static final int MIN

heap

protected Array heap

Constructor Detail

BinaryHeap

public BinaryHeap(int size,
                  int type)

Method Detail

initMemory

protected void initMemory(int arraySize)

extractFirst

public java.lang.Object extractFirst()

Description copied from interface: PriorityQueue

Get the element with greatest priority out of the queue

Specified by:

extractFirst in interface PriorityQueue

Following copied from interface: brutil.PriorityQueue

Returns:

The object with the greatest priority.

getData

public java.lang.Object getData(Handle handle)

getFirstKey

public java.lang.Comparable getFirstKey()

Description copied from interface: PriorityQueue

Get the key of the object with greatest priority.

Specified by:

getFirstKey in interface PriorityQueue

Following copied from interface: brutil.PriorityQueue

Returns:

The key of the object with greatest priority.

getKey

public java.lang.Object getKey(Handle handle)

getType

public int getType()

insert

public Handle insert(java.lang.Comparable key,
                     java.lang.Object data)

Places the specified element into the heap and arranges it based on the value of key.

Specified by:

insert in interface PriorityQueue

Parameters:

key - - Used to specify the importance of the data in the heap.

data - - the value to be stored.

createHandle

protected Handle createHandle(int index)

createElement

protected BinaryHeap.Element createElement(java.lang.Comparable key,
                                           Handle handle,
                                           java.lang.Object data)

isEmpty

public boolean isEmpty()

Description copied from interface: Collection

Returns true if the Collection contains no elements, false otherwise

Specified by:

isEmpty in interface Collection

Returns:

true if the heap is empty. false otherwise.

updateKey

public boolean updateKey(Handle handle,
                         java.lang.Comparable newKey)

Changes the key of the entry with the specified handle to the newKey.

Specified by:

updateKey in interface PriorityQueue

Parameters:

handle - - points to the entry to be updated

newKey - - the new comparable value that should be associated with handle.

Returns:

- true: key was updated successfully. false otherwise.

size

public int size()

Description copied from interface: Collection

Returns the size of the given Collection.

Specified by:

size in interface Collection

clear

public void clear()

Description copied from interface: Collection

Clears out the contents of the Collection (optional operation)

Specified by:

clear in interface Collection

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object