edu.jhu.ece.iacl.jist.structures.data
Class BinaryMinHeap

java.lang.Object
  edu.jhu.ece.iacl.jist.structures.data.BinaryMinHeap

public class BinaryMinHeap
extends java.lang.Object

Implements a binary heap. Note that all "matching" is based on the compareTo method.

Author:

Mark Allen Weiss

Constructor Summary

BinaryMinHeap(Indexable[] items)
Construct the binary heap from an array.

BinaryMinHeap(int capacity, int XN, int YN, int ZN)
Instantiates a new binary min heap.

Method Summary

void	add(Indexable x) Insert into the priority queue.
void	change(Indexable node, java.lang.Comparable value) Change.
void	change(int i, int j, int k, Indexable x) Change.
protected void	change(int i, int j, int k, int chainIndex, java.lang.Comparable value) Change.
boolean	isEmpty() Test if the priority queue is logically empty.
void	makeEmpty() Make the priority queue logically empty.
Indexable	peek() Find the smallest item in the priority queue.
void	percolateUp(int k) Percolate up.
Indexable	remove() Remove the smallest item from the priority queue.
int	size() Returns size.

Methods inherited from class java.lang.Object

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

Constructor Detail

BinaryMinHeap

public BinaryMinHeap(int capacity,
                     int XN,
                     int YN,
                     int ZN)

Instantiates a new binary min heap.

Parameters:

capacity - the capacity

XN - the xN

YN - the yN

ZN - the zN

BinaryMinHeap

public BinaryMinHeap(Indexable[] items)

Construct the binary heap from an array.

Parameters:

items - the inital items in the binary heap.

Method Detail

add

public void add(Indexable x)

Insert into the priority queue. Duplicates are allowed.

Parameters:

x - the item to insert.

percolateUp

public void percolateUp(int k)

Percolate up.

Parameters:

k - the k

change

public void change(Indexable node,
                   java.lang.Comparable value)

Change.

Parameters:

node - the node

value - the value

change

protected void change(int i,
                      int j,
                      int k,
                      int chainIndex,
                      java.lang.Comparable value)

Change.

Parameters:

i - the i

j - the j

k - the k

chainIndex - the chain index

value - the value

change

public void change(int i,
                   int j,
                   int k,
                   Indexable x)

Change.

Parameters:

i - the i

j - the j

k - the k

x - the x

peek

public Indexable peek()

Find the smallest item in the priority queue.

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

remove

public Indexable remove()

Remove the smallest item from the priority queue.

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Returns:

true if empty, false otherwise.

size

public int size()

Returns size.

Returns:

current size.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.