Package org.drip.graph.heap

Class BinomialTree<KEY extends java.lang.Comparable<KEY>,ITEM>

java.lang.Object

org.drip.graph.heap.BinomialTree<KEY,ITEM>

public class BinomialTree<KEY extends java.lang.Comparable<KEY>,ITEM>
extends java.lang.Object

BinomialTree implements an Ordered Binomial Tree. The References are:

• Brodal, G. S., and C. Okasaki (1996): Optimal Purely Functional Priority Queues Journal of Functional Programming 6 (6) 839-857
• Brown, M. R. (1978): Implementation and Analysis of Binomial Queue Algorithms SIAM Journal on Computing 7 (3) 298-319
• Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3^rd Edition MIT Press
• Vuillemin, J. (1978): A Data Structure for Manipulating Priority Queues Communications of the ACM 21 (4) 309-315
• Wikipedia (2019): Binomial Heap https://en.wikipedia.org/wiki/Binomial_heap

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Heap Based Priority Queue Implementations

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
BinomialTree(PriorityQueueEntry<KEY,ITEM> entry)	BinomialTree Constructor

Method Summary

Modifier and Type	Method	Description
java.util.List<KEY>	childKeyList()	Retrieve the List of all the Child Keys
java.util.List<BinomialTree<KEY,ITEM>>	children()	Retrieve the List of the Children
static <KEY extends java.lang.Comparable<KEY>, ITEM> BinomialTree<KEY,ITEM>	CombinePair(BinomialTree<KEY,ITEM> binomialTree1, BinomialTree<KEY,ITEM> binomialTree2, boolean minHeap)	Combine the specified Pair of Binomial Trees into one of the Higher Order
PriorityQueueEntry<KEY,ITEM>	entry()	Retrieve the Entry of the Binomial Tree Node
int	order()	Retrieve the Order of the Binomial Tree
BinomialTree<KEY,ITEM>	parent()	Retrieve the Parent of the Binomial Tree
boolean	setChildren(java.util.List<BinomialTree<KEY,ITEM>> children)	Set the Children of the Binomial Tree
boolean	setParent(BinomialTree<KEY,ITEM> parent)	Set the Parent of the Binomial Tree
java.lang.String	toString()

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

BinomialTree

public BinomialTree(PriorityQueueEntry<KEY,ITEM> entry)
             throws java.lang.Exception

BinomialTree Constructor

Parameters:

entry - Entry

Throws:

java.lang.Exception - Thrown if the Inputs are Invalid

Method Details

CombinePair

public static <KEY extends java.lang.Comparable<KEY>,
ITEM>
BinomialTree<KEY,ITEM> CombinePair(BinomialTree<KEY,ITEM> binomialTree1,
BinomialTree<KEY,ITEM> binomialTree2,
boolean minHeap)

Combine the specified Pair of Binomial Trees into one of the Higher Order

Type Parameters:

KEY - Key Type

ITEM - Item Type

Parameters:

binomialTree1 - Binomial Tree #1

binomialTree2 - Binomial Tree #2

minHeap - TRUE - Meld into a Minimum Binomial Heap

Returns:

The Binomial Tree of Higher Order

entry

public PriorityQueueEntry<KEY,ITEM> entry()

Retrieve the Entry of the Binomial Tree Node

Returns:

Entry of the Binomial Tree Node

parent

public BinomialTree<KEY,ITEM> parent()

Retrieve the Parent of the Binomial Tree

Returns:

Parent of the Binomial Tree

children

public java.util.List<BinomialTree<KEY,ITEM>> children()

Retrieve the List of the Children

Returns:

List of the Children

order

public int order()

Retrieve the Order of the Binomial Tree

Returns:

Order of the Binomial Tree

setParent

public boolean setParent(BinomialTree<KEY,ITEM> parent)

Set the Parent of the Binomial Tree

Parameters:

parent - Parent of the Binomial Tree

Returns:

TRUE - The Parent of the Binomial Tree successfully set

setChildren

public boolean setChildren(java.util.List<BinomialTree<KEY,ITEM>> children)

Set the Children of the Binomial Tree

Parameters:

children - Children of the Binomial Tree

Returns:

TRUE - The Children of the Binomial Tree successfully set

childKeyList

public java.util.List<KEY> childKeyList()

Retrieve the List of all the Child Keys

Returns:

The List of all the Child Keys

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object