org.placelab.util
Class DHeap

java.lang.Object
  org.placelab.util.DHeap

All Implemented Interfaces:

PriorityQueue

public class DHeap

extends java.lang.Object

implements PriorityQueue

Field Summary

protected java.util.Comparator	comparator
protected java.lang.Object[]	data

Constructor Summary

DHeap(java.util.Comparator c, int dSize)
Default Constructor.

DHeap(java.util.Comparator c, int dSize, int capacity)
Other Constructor.

Method Summary

java.lang.Object	deleteMin() Returns and removes the smallest object in the heap.
java.lang.Object	findMin() Find the smallest item in the heap.
void	insert(java.lang.Object x) Inserts a new object to the priority queue
boolean	isEmpty() Returns true if priority queue has no elements
static void	main(java.lang.String[] args)
void	makeEmpty() Makes the heap empty by replacing the old data array with a new empty one of size initialSize.
protected void	percolateDown(int startNode) Method to percolate down from a given node in the heap.
protected void	percolateUp(int startNode) Method to percolate up from a given node in the heap.
boolean	remove(java.lang.Object o) Removes the requested element from the queue, if it exists.
int	size() Finds the size of the heap
java.lang.String	toString() Returns a level-order traversal of the heap

Methods inherited from class java.lang.Object

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

Field Detail

data

protected java.lang.Object[] data

comparator

protected java.util.Comparator comparator

Constructor Detail

DHeap

public DHeap(java.util.Comparator c,
             int dSize)

Default Constructor. Initializes the heap with the default capacity.

Parameters:

c - an instance of the comparator to use for ordering the heap

dSize - the number of children a node can have (>=2)

DHeap

public DHeap(java.util.Comparator c,
             int dSize,
             int capacity)

Other Constructor. Lets you initialize the heap to whatever capacity you want.

Parameters:

c - an instance of the comparator to use for ordering the heap

dSize - the number of children a node can have (>=2)

capacity - the initial size of the heap (>=1)

Method Detail

size

public int size()

Finds the size of the heap

Returns:

the size of the heap

remove

public boolean remove(java.lang.Object o)

Removes the requested element from the queue, if it exists.

Returns:

true if element found and removed false otherwise.

isEmpty

public boolean isEmpty()

Description copied from interface: PriorityQueue

Returns true if priority queue has no elements

Specified by:

isEmpty in interface PriorityQueue

Returns:

if the heap is empty or not

findMin

public java.lang.Object findMin()

Find the smallest item in the heap.

Specified by:

findMin in interface PriorityQueue

Returns:

the smallest item

Throws:

EmptyHeapException - if heap is empty

insert

public void insert(java.lang.Object x)

Description copied from interface: PriorityQueue

Inserts a new object to the priority queue

Specified by:

insert in interface PriorityQueue

Parameters:

x - Object to be inserted into the priority queue.

deleteMin

public java.lang.Object deleteMin()

Returns and removes the smallest object in the heap.

Specified by:

deleteMin in interface PriorityQueue

Returns:

the smallest object

Throws:

EmptyHeapException - if the heap is empty

makeEmpty

public void makeEmpty()

Makes the heap empty by replacing the old data array with a new empty one of size initialSize.

Specified by:

makeEmpty in interface PriorityQueue

percolateUp

protected void percolateUp(int startNode)

Method to percolate up from a given node in the heap.

Parameters:

startNode - the index of the node at which the percolate begins.

percolateDown

protected void percolateDown(int startNode)

Method to percolate down from a given node in the heap. The runtime for percolateDown ought to be O(d log(base d) n) since d time to find smallest node for log(base d) n levels

Parameters:

startNode - the index of the node at which the percolate begins.

toString

public java.lang.String toString()

Returns a level-order traversal of the heap

Returns:

the string representation

main

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