gov.nist.antd.merlin.algorithm.route.util
Class BinaryHeap

java.lang.Object
  |
  +--gov.nist.antd.merlin.algorithm.route.util.BinaryHeap

All Implemented Interfaces:

PriorityQueue

public class BinaryHeap

extends java.lang.Object

implements PriorityQueue

This class implements a binary heap.

 This class was developed at the National Institute of Standards and
 Technology by employees of the Federal Government in the course of
 their official duties. Pursuant to title 17 Section 105 of the United
 States Code this software is not subject to copyright protection and
 is in the public domain.
 NIST assumes no responsibility whatsoever for its use by other parties,
 and makes no guarantees, expressed or implied, about its quality,
 reliability, or any other characteristic.
 

 We would appreciate acknowledgement if the software is used.
 

 NIST ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION AND
 DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER RESULTING
 FROM THE USE OF THIS SOFTWARE.
 

Author:

borchert

, rouil

Nested Class Summary

Nested classes inherited from class gov.nist.antd.merlin.algorithm.route.util.PriorityQueue

PriorityQueue.Position

Field Summary

private java.lang.Comparable[]	array The heap array
private int	currentSize Number of elements in heap
private static int	DEFAULT_CAPACITY Default capacity of this binary heap

Constructor Summary

BinaryHeap()
Default constructor

BinaryHeap(java.lang.Comparable[] items)
Construct the binary heap from an array.

Method Summary

private void	buildHeap() Establish heap order property from an arbitrary arrangement of items.
void	decreaseKey(PriorityQueue.Position p, java.lang.Comparable newVal) Decrease the Key.
java.lang.Comparable	deleteMin() Remove the smallest item from the priority queue.
private void	doubleArray() Internal method to extend array.
java.lang.Comparable	findMin() Find the smallest item in the priority queue.
PriorityQueue.Position	insert(java.lang.Comparable x) Insert into the priority queue.
boolean	isEmpty() Test if the priority queue is logically empty.
void	makeEmpty() Make the priority queue logically empty.
private void	percolateDown(int hole) Internal method to percolate down in the heap.
int	size() Returns size.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_CAPACITY

private static final int DEFAULT_CAPACITY

Default capacity of this binary heap

See Also:

Constant Field Values

currentSize

private int currentSize

Number of elements in heap

array

private java.lang.Comparable[] array

The heap array

Constructor Detail

BinaryHeap

public BinaryHeap()

Default constructor

BinaryHeap

public BinaryHeap(java.lang.Comparable[] items)

Construct the binary heap from an array.

Parameters:

items - the inital items in the binary heap.

Method Detail

insert

public PriorityQueue.Position insert(java.lang.Comparable x)

Insert into the priority queue. Duplicates are allowed.

Specified by:

insert in interface PriorityQueue

Parameters:

x - the item to insert.

Returns:

null, signifying that decreaseKey cannot be used.

decreaseKey

public void decreaseKey(PriorityQueue.Position p,
                        java.lang.Comparable newVal)

Decrease the Key. Not used in a binary queue.

Specified by:

decreaseKey in interface PriorityQueue

Parameters:

p - The Position of the key.

newVal - The new value.

findMin

public java.lang.Comparable findMin()

Find the smallest item in the priority queue.

Specified by:

findMin in interface PriorityQueue

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

deleteMin

public java.lang.Comparable deleteMin()

Remove the smallest item from the priority queue.

Specified by:

deleteMin in interface PriorityQueue

Returns:

the smallest item.

Throws:

UnderflowException - if empty.

buildHeap

private void buildHeap()

Establish heap order property from an arbitrary arrangement of items. Runs in linear time.

isEmpty

public boolean isEmpty()

Test if the priority queue is logically empty.

Specified by:

isEmpty in interface PriorityQueue

Returns:

true if empty, false otherwise.

size

public int size()

Returns size.

Specified by:

size in interface PriorityQueue

Returns:

current size.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

Specified by:

makeEmpty in interface PriorityQueue

percolateDown

private void percolateDown(int hole)

Internal method to percolate down in the heap.

Parameters:

hole - the index at which the percolate begins.

doubleArray

private void doubleArray()

Internal method to extend array.