Package org.drip.graph.softheap

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

java.lang.Object
org.drip.graph.softheap.KaplanZwickBinaryNode<KEY,​ITEM>
public class KaplanZwickBinaryNode<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends java.lang.Object
KaplanZwickBinaryNode implements the Binary Node 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

    • KaplanZwickBinaryNode

      public KaplanZwickBinaryNode​(boolean minHeap, int r, int k) throws java.lang.Exception
      KaplanZwickBinaryNode Constructor
      Parameters:
      minHeap - Min Heap Flag
      r - R Parameter
      k - Rank
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • CombineRootNodePair

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> KaplanZwickBinaryNode<KEY,​ITEM> CombineRootNodePair​(KaplanZwickBinaryNode<KEY,​ITEM> node1, KaplanZwickBinaryNode<KEY,​ITEM> node2)
      Combine Two Root Nodes of Rank k each to a Root Node of Rank k + 1
      Type Parameters:
      KEY - Key Type
      ITEM - Item Type
      Parameters:
      node1 - Node #1
      node2 - Node #2
      Returns:
      The Combined Root Node of Rank k + 1

    • FromErrorRate

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> KaplanZwickBinaryNode<KEY,​ITEM> FromErrorRate​(boolean minHeap, double errorRate, int k, KaplanZwickBinaryNode<KEY,​ITEM> left, KaplanZwickBinaryNode<KEY,​ITEM> right, KaplanZwickBinaryNode<KEY,​ITEM> parent)
      Construct an Instance of KaplanZwickBinaryNode from the Error Rate
      Type Parameters:
      KEY - Key Type
      ITEM - Item Type
      Parameters:
      minHeap - Min Heap Flag
      errorRate - Error Rate
      k - Rank
      left - Left Child
      right - Right Child
      parent - Parent
      Returns:
      KaplanZwickBinaryNode Instance from the Error Rate

    • LeafRoot

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> KaplanZwickBinaryNode<KEY,​ITEM> LeafRoot​(boolean minHeap, int r, PriorityQueueEntry<KEY,​ITEM> entry)
      Construct a Leaf Root Node of a New 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 Leaf Root of a New Tree with a single KeEntryy

    • minHeap

      public boolean minHeap()
      Indicate if the Binary Heap is a Min Heap
      Returns:
      TRUE - The Binary Heap is a Min Heap

    • k

      public int k()
      Retrieve the Rank
      Returns:
      The Rank

    • left

      public KaplanZwickBinaryNode<KEY,​ITEM> left()
      Retrieve the Left Tree
      Returns:
      The Left Tree

    • right

      public KaplanZwickBinaryNode<KEY,​ITEM> right()
      Retrieve the Right Tree
      Returns:
      The right Tree

    • parent

      public KaplanZwickBinaryNode<KEY,​ITEM> parent()
      Retrieve the Parent Tree
      Returns:
      The Parent Tree

    • targetSize

      public KaplanZwickTargetSize targetSize()
      Retrieve the Target Size
      Returns:
      The Target Size

    • r

      public int r()
      Retrieve the R Parameter
      Returns:
      The R Parameter

    • entryList

      public java.util.List<PriorityQueueEntry<KEY,​ITEM>> entryList()
      Retrieve the List of Entries
      Returns:
      The List of Entries

    • cEntry

      public PriorityQueueEntry<KEY,​ITEM> cEntry()
      Retrieve the cEntry
      Returns:
      The cEntry

    • currentSize

      public int currentSize()
      Retrieve the Current Size of the List
      Returns:
      Current Size of the List

    • setCEntry

      public boolean setCEntry​(PriorityQueueEntry<KEY,​ITEM> cEntry)
      Set the CEntry of the Current Node
      Parameters:
      cEntry - The CEntry
      Returns:
      TRUE - The cEntry of the Current Node successfully set

    • setParent

      public boolean setParent​(KaplanZwickBinaryNode<KEY,​ITEM> parent)
      Set the Parent of the Current Node
      Parameters:
      parent - The Parent
      Returns:
      TRUE - The Parent of the Current Node successfully set

    • setLeft

      public boolean setLeft​(KaplanZwickBinaryNode<KEY,​ITEM> left)
      Set the Left Child of the Current Node
      Parameters:
      left - The Left Child
      Returns:
      TRUE - The Left Child of the Current Node successfully set

    • setRight

      public boolean setRight​(KaplanZwickBinaryNode<KEY,​ITEM> right)
      Set the Right Child of the Current Node
      Parameters:
      right - The Right Child
      Returns:
      TRUE - The Right Child of the Current Node successfully set

    • addEntry

      public boolean addEntry​(PriorityQueueEntry<KEY,​ITEM> entry)
      Add an Entry to the Entry List
      Parameters:
      entry - The Entry
      Returns:
      TRUE - The Entry is successfully added to the Entry List

    • peekTopEntry

      public PriorityQueueEntry<KEY,​ITEM> peekTopEntry()
      Peek the Top Entry
      Returns:
      The Top Entry

    • removeTopEntry

      public PriorityQueueEntry<KEY,​ITEM> removeTopEntry()
      Remove the Top Entry
      Returns:
      The Top Entry

    • keyCorruptionStatusList

      public java.util.List<java.lang.Boolean> keyCorruptionStatusList()
      Retrieve the Key Corruption Status List
      Returns:
      The Key Corruption Status List

    • isRoot

      public boolean isRoot()
      Indicate if the Node is a Root
      Returns:
      TRUE - The Node is a Root

    • isLeaf

      public boolean isLeaf()
      Indicate if the Node is a Leaf
      Returns:
      TRUE - The Node is a Leaf

    • sift

      public boolean sift()
      Sift the Node
      Returns:
      TRUE - The Node has been successfully sifted

    • bfsWalk

      public java.util.List<KaplanZwickBinaryNode<KEY,​ITEM>> bfsWalk()
      Perform a BFS Walk through the Nodes and retrieve them
      Returns:
      The List of Nodes

    • childKeyList

      public java.util.List<PriorityQueueEntry<KEY,​ITEM>> childKeyList()
      Perform a BFS Walk through the Nodes and retrieve them
      Returns:
      The List of Nodes

    • toString

      public java.lang.String toString()
      Overrides:
      toString in class java.lang.Object