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

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

All Implemented Interfaces:

PriorityQueue

public class PairingHeap

extends java.lang.Object

implements PriorityQueue

This class is the representation of queue

 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

private static class

PairingHeap.PairNode Private static class for use with PairHeap.

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

Field Summary

private PairingHeap.PairNode	root The root noot the the pairing heap
private int	theSize The current size
private PairingHeap.PairNode[]	treeArray The tree array for combineSiblings

Constructor Summary

PairingHeap()
Construct the pairing heap.

Method Summary

private PairingHeap.PairNode	combineSiblings(PairingHeap.PairNode firstSibling) Internal method that implements two-pass merging.
private PairingHeap.PairNode	compareAndLink(PairingHeap.PairNode first, PairingHeap.PairNode second) Internal method that is the basic operation to maintain order.
void	decreaseKey(PriorityQueue.Position pos, java.lang.Comparable newVal) Change the value of the item stored in the pairing heap.
java.lang.Comparable	deleteMin() Remove the smallest item from the priority queue.
private PairingHeap.PairNode[]	doubleIfFull(PairingHeap.PairNode[] array, int index) Double the size of the Heap full
java.lang.Comparable	findMin() Find the smallest item in the priority queue.
PriorityQueue.Position	insert(java.lang.Comparable x) Insert into the priority queue, and return a Position that can be used by decreaseKey.
boolean	isEmpty() Test if the priority queue is logically empty.
void	makeEmpty() Make the priority queue logically empty.
int	size() Returns number of items stored in the priority queue.

Methods inherited from class java.lang.Object

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

Field Detail

root

private PairingHeap.PairNode root

The root noot the the pairing heap

theSize

private int theSize

The current size

treeArray

private PairingHeap.PairNode[] treeArray

The tree array for combineSiblings

Constructor Detail

PairingHeap

public PairingHeap()

Construct the pairing heap.

Method Detail

insert

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

Insert into the priority queue, and return a Position that can be used by decreaseKey. Duplicates are allowed.

Specified by:

insert in interface PriorityQueue

Parameters:

x - the item to insert.

Returns:

the node containing the newly inserted item.

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 pairing heap is 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 pairing heap is empty.

decreaseKey

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

Change the value of the item stored in the pairing heap.

Specified by:

decreaseKey in interface PriorityQueue

Parameters:

pos - any Position returned by insert.

newVal - the new value, which must be smaller than the currently stored value.

Throws:

java.lang.IllegalArgumentException - if pos is null.

IllegalValueException - if new value is larger than old.

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 number of items stored in the priority queue.

Specified by:

size in interface PriorityQueue

Returns:

size of the priority queue.

makeEmpty

public void makeEmpty()

Make the priority queue logically empty.

Specified by:

makeEmpty in interface PriorityQueue

compareAndLink

private PairingHeap.PairNode compareAndLink(PairingHeap.PairNode first,
                                            PairingHeap.PairNode second)

Internal method that is the basic operation to maintain order. Links first and second together to satisfy heap order.

Parameters:

first - root of tree 1, which may not be null. first.nextSibling MUST be null on entry.

second - root of tree 2, which may be null.

Returns:

result of the tree merge.

doubleIfFull

private PairingHeap.PairNode[] doubleIfFull(PairingHeap.PairNode[] array,
                                            int index)

Double the size of the Heap full

Parameters:

array - The list of PairNode

index - The index of the top element

Returns:

a new array with double size if full

combineSiblings

private PairingHeap.PairNode combineSiblings(PairingHeap.PairNode firstSibling)

Internal method that implements two-pass merging.

Parameters:

firstSibling - the root of the conglomerate; assumed not null.

Returns:

the new PairNode root.