Package org.drip.graph.softheap

Class KaplanZwickTreeMelder<KEY extends java.lang.Comparable<KEY>,​ITEM>

java.lang.Object
org.drip.graph.softheap.KaplanZwickTreeMelder<KEY,​ITEM>
public class KaplanZwickTreeMelder<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends java.lang.Object
KaplanZwickTreeMelder grows the Melded Tree List. The References are:

  • Chazelle, B. (2000): The Discrepancy Method: Randomness and Complexity https://www.cs.princeton.edu/~chazelle/pubs/book.pdf
  • Chazelle, B. (2000): The Soft Heap: An Approximate Priority Queue with Optimal Error Rate Journal of the Association for Computing Machinery 47 (6) 1012-1027
  • Chazelle, B. (2000): A Minimum Spanning Tree Algorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047
  • Kaplan, H., and U. Zwick (2009): A simpler implementation and analysis of Chazelle's Soft Heaps https://epubs.siam.org/doi/abs/10.1137/1.9781611973068.53?mobileUi=0
  • Pettie, S., and V. Ramachandran (2008): Randomized Minimum Spanning Tree Algorithms using Exponentially Fewer Random Bits ACM Transactions on Algorithms 4 (1) 1-27




Author:
Lakshmi Krishnamurthy

  • Constructor Details

    • KaplanZwickTreeMelder

      public KaplanZwickTreeMelder​(KaplanZwickTree<KEY,​ITEM> mergedTreeList) throws java.lang.Exception
      KaplanZwickTreeMelder Constructor
      Parameters:
      mergedTreeList - The Merged Tree List
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • head

      public KaplanZwickTree<KEY,​ITEM> head()
      Retrieve the Head of the Melded Tree
      Returns:
      Head of the Melded Tree

    • tail

      public KaplanZwickTree<KEY,​ITEM> tail()
      Retrieve the Tail of the Melded Tree
      Returns:
      Tail of the Melded Tree

    • tailRank

      public int tailRank()
      Retrieve the Rank of the Tail
      Returns:
      Rank of the Tail

    • growTail

      public boolean growTail​(KaplanZwickBinaryNode<KEY,​ITEM> rootNode)
      Grow the Tail Root Node using the Supplied Root Node
      Parameters:
      rootNode - Root Node
      Returns:
      TRUE - The Tail Root Node grown successfully using the Supplied Root Node

    • appendToTail

      public boolean appendToTail​(KaplanZwickTree<KEY,​ITEM> tail)
      Append to the Tail using the New Tail
      Parameters:
      tail - The New Tail
      Returns:
      TRUE - The Tail Root Node appended successfully using the Supplied Root Node