Package org.drip.graph.softheap

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

java.lang.Object
org.drip.graph.softheap.KaplanZwickTree<KEY,​ITEM>
public class KaplanZwickTree<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends java.lang.Object
KaplanZwickTree implements the Tree described in Kaplan and Zwick (2009). 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

    • KaplanZwickTree

      public KaplanZwickTree​(KaplanZwickBinaryNode<KEY,​ITEM> root) throws java.lang.Exception
      KaplanZwickTree Constructor
      Parameters:
      root - Root of the Current Tree
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • UpdateSuffixExtremum

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> boolean UpdateSuffixExtremum​(KaplanZwickTree<KEY,​ITEM> tree)
      Update the Suffix Extremum of all Trees at and preceding the specified Tree
      Type Parameters:
      KEY - Key Type
      ITEM - Item Type
      Parameters:
      tree - Specified Tree
      Returns:
      TRUE - Update Suffix Extremum successfully completed

    • EquiRankTreeMerge

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> KaplanZwickTree<KEY,​ITEM> EquiRankTreeMerge​(KaplanZwickTree<KEY,​ITEM> tree1, KaplanZwickTree<KEY,​ITEM> tree2)
      Merge Two Trees with Identical Ranks
      Type Parameters:
      KEY - Key Type
      ITEM - Item Type
      Parameters:
      tree1 - Tree #1
      tree2 - Tree #2
      Returns:
      The Merged Tree

    • Initial

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> KaplanZwickTree<KEY,​ITEM> Initial​(boolean minHeap, int r, PriorityQueueEntry<KEY,​ITEM> entry)
      Construct an Initial Tree with a single Entry
      Type Parameters:
      KEY - Key Type
      ITEM - Item Type
      Parameters:
      minHeap - Min Heap Flag
      r - The R Parameter
      entry - The Entry
      Returns:
      The Initial Tree with a single Entry

    • root

      public KaplanZwickBinaryNode<KEY,​ITEM> root()
      Retrieve the Root of the Tree
      Returns:
      The Root

    • prev

      public KaplanZwickTree<KEY,​ITEM> prev()
      Retrieve the Previous Tree in the List
      Returns:
      The Previous Tree in the List

    • next

      public KaplanZwickTree<KEY,​ITEM> next()
      Retrieve the Next Tree in the List
      Returns:
      The Next Tree in the List

    • suffixExtremum

      public KaplanZwickTree<KEY,​ITEM> suffixExtremum()
      Retrieve the Extremum ckey Tree among those following this in the List
      Returns:
      The Extremum ckey Tree among those following this in the List

    • rank

      public int rank()
      Retrieve the Rank of the Tree
      Returns:
      Rank of the Tree

    • setRoot

      public boolean setRoot​(KaplanZwickBinaryNode<KEY,​ITEM> root)
      (Re-)set the Root
      Parameters:
      root - The Root
      Returns:
      TRUE - The Root successfully (re-)set

    • setPrev

      public boolean setPrev​(KaplanZwickTree<KEY,​ITEM> prev)
      (Re-)set the Previous Tree
      Parameters:
      prev - The Previous Tree
      Returns:
      TRUE - The Previous Tree successfully (re-)set

    • setNext

      public boolean setNext​(KaplanZwickTree<KEY,​ITEM> next)
      (Re-)set the Next Tree
      Parameters:
      next - The Next Tree
      Returns:
      TRUE - The Next Tree successfully (re-)set

    • setSuffixExtremum

      public boolean setSuffixExtremum​(KaplanZwickTree<KEY,​ITEM> suffixExtremum)
      (Re-)set the Suffix Extremum Tree
      Parameters:
      suffixExtremum - The Suffix Extremum
      Returns:
      TRUE - The Suffix Extremum Tree successfully (re-)set

    • rootTree

      public KaplanZwickTree<KEY,​ITEM> rootTree()
      Generate a Stand-alone Tree with the Root Node alone in its List
      Returns:
      Stand-alone Tree with the Root Node alone in its List