scranton.tree
Class HeapViaArray

java.lang.Object
  scranton.tree.HeapViaArray

All Implemented Interfaces:

Heap

Direct Known Subclasses:

PriorityQueueViaHeapArray

public class HeapViaArray

extends java.lang.Object

implements Heap

Heap Class: Manages a heap in an array applying a comparator. The class includes several utilities fall into two categories 1. Methods to support the heap-to-array relationship and the corresponding index calculations 2. The code for the siftUp and siftDown methods

Field Summary

protected java.util.Comparator	c c.compare(a,b)<0 implies a precedes b
protected java.lang.Object[]	heap The array that holds the heap
protected int	heapSize The size of the heap

Constructor Summary

HeapViaArray(java.util.Comparator comp)
Method Heap construct a heap with Comparator c and initially of size max.

HeapViaArray(java.util.Comparator comp, int max)
Method Heap construct a heap with Comparator c and initially of size max.

HeapViaArray(java.lang.Object[] data, int actual, java.util.Comparator comp)
Method Heap construct a heap from an exisitng array of data with.

Method Summary

java.lang.Object[]	close() Method close terminates the heap and returns the current array.
private java.lang.Object[]	doubler(java.lang.Object[] oldHeap) Method doubler doubles the size of the array instead of reporting an overflow error.
void	insert(java.lang.Object val) Method insert a new object and reorganize the heap by applying the siftUp process.
private boolean	isLeaf(int currentNode) Method isLeaf.
private int	leftchild(int currentNode) Method leftchild.
private int	parent(int currentNode) Method parent.
java.lang.Object	remove() Method remove removes the root and applies the siftDown process to maintain the heap correctly.
private int	rightchild(int currentNode) Method rightchild.
private void	siftDown(int currentNode) Method siftDown implements the siftDown process.
private void	siftUp(int curr) Method siftUp apply the siftUp method starting at curr.
int	size() Method size reports the current size of the heap.
private void	swap(int i, int j) Method swap interchanges two objects in the array.

Methods inherited from class java.lang.Object

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

Field Detail

c

protected java.util.Comparator c

c.compare(a,b)<0 implies a precedes b

heap

protected java.lang.Object[] heap

The array that holds the heap

heapSize

protected int heapSize

The size of the heap

Constructor Detail

HeapViaArray

public HeapViaArray(java.util.Comparator comp)

Method Heap construct a heap with Comparator c and initially of size max.

Parameters:

comp - The comparator that applies the heap order

HeapViaArray

public HeapViaArray(java.util.Comparator comp,
                    int max)

Method Heap construct a heap with Comparator c and initially of size max.

Parameters:

max -

comp -

HeapViaArray

public HeapViaArray(java.lang.Object[] data,
                    int actual,
                    java.util.Comparator comp)

Method Heap construct a heap from an exisitng array of data with.

Parameters:

data - - an array of Objects

actual - - the number of Objects

comp - - the heap order

Method Detail

size

public int size()

Method size reports the current size of the heap.

Specified by:

size in interface Heap

Returns:

int Returns the size of the heap

insert

public void insert(java.lang.Object val)

Method insert a new object and reorganize the heap by applying the siftUp process.

Specified by:

insert in interface Heap

Parameters:

val -

remove

public java.lang.Object remove()

Method remove removes the root and applies the siftDown process to maintain the heap correctly.

Specified by:

remove in interface Heap

Returns:

Object - the root of the heap

close

public java.lang.Object[] close()

Method close terminates the heap and returns the current array. NOTE: One should first use the size method to determine the number of Objects in the heap.

Returns:

Object[]

isLeaf

private boolean isLeaf(int currentNode)

Method isLeaf.

Parameters:

currentNode - - index of the currentNode

Returns:

boolean returns true iff currentNode is the index of a leaf node

leftchild

private int leftchild(int currentNode)

Method leftchild.

Parameters:

currentNode - - array index of currentNode

Returns:

int returns the index of the leftChild of the currentNode

rightchild

private int rightchild(int currentNode)

Method rightchild.

Parameters:

currentNode - - array index of current node

Returns:

int returns the index of the rightChild of the currentNode

parent

private int parent(int currentNode)

Method parent.

Parameters:

currentNode - - array index of current node

Returns:

int - returns the index of the parent

swap

private void swap(int i,
                  int j)

Method swap interchanges two objects in the array.

Parameters:

i - - array index of one Object

j - - array index of other Object

doubler

private java.lang.Object[] doubler(java.lang.Object[] oldHeap)

Method doubler doubles the size of the array instead of reporting an overflow error.

Parameters:

oldHeap - current heap

Returns:

Object[] new heap that is twice as big

siftUp

private void siftUp(int curr)

Method siftUp apply the siftUp method starting at curr. The timing for this method is O(log(heap size))

Parameters:

curr - - start position of siftUp method

siftDown

private void siftDown(int currentNode)

Method siftDown implements the siftDown process. The timing for this method is O(log(heap size))

Parameters:

currentNode - - start position of the siftDown process