Package org.drip.graph.softheap

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

java.lang.Object
org.drip.graph.heap.PriorityQueue<KEY,​ITEM>
org.drip.graph.softheap.KaplanZwickPriorityQueue<KEY,​ITEM>
public class KaplanZwickPriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends PriorityQueue<KEY,​ITEM>
KaplanZwickPriorityQueue implements the Soft Heap 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

    • KaplanZwickPriorityQueue

      public KaplanZwickPriorityQueue​(boolean minHeap, int r, KaplanZwickTree<KEY,​ITEM> head, KaplanZwickTree<KEY,​ITEM> tail) throws java.lang.Exception
      KaplanZwickPriorityQueue Constructor
      Parameters:
      minHeap - TRUE - Indicates that Heap is a Min Heap
      r - R Parameter
      head - The Head Tree of the Heap
      tail - The Tail Tree of the Heap
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • Meld

      public static <KEY extends java.lang.Comparable<KEY>,​ ITEM> KaplanZwickPriorityQueue<KEY,​ITEM> Meld​(KaplanZwickPriorityQueue<KEY,​ITEM> queue1, KaplanZwickPriorityQueue<KEY,​ITEM> queue2)
      Meld the Queue Pair into a Queue
      Type Parameters:
      KEY - Key Type
      ITEM - Item Type
      Parameters:
      queue1 - Queue #1
      queue2 - Queue #2
      Returns:
      The Melded Queue

    • Initial

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

    • head

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

    • tail

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

    • r

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

    • rank

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

    • meld

      public boolean meld​(PriorityQueue<KEY,​ITEM> priorityQueueOther)
      Description copied from class: PriorityQueue
      Meld the Specified Priority Queue with the Current
      Specified by:
      meld in class PriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
      Parameters:
      priorityQueueOther - The Specified Binary Tree Priority Queue
      Returns:
      TRUE - The Specified Priority Queue successfully melded

    • insert

      public boolean insert​(KEY key, ITEM item)
      Description copied from class: PriorityQueue
      Insert the Specified Key/Item into the Heap
      Specified by:
      insert in class PriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
      Parameters:
      key - Key
      item - Node Item
      Returns:
      TRUE - The Key/Item successfully inserted

    • isEmpty

      public boolean isEmpty()
      Description copied from class: PriorityQueue
      Indicate if the Heap is Empty
      Specified by:
      isEmpty in class PriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
      Returns:
      TRUE - The Heap is Empty

    • extremum

      public PriorityQueueEntry<KEY,​ITEM> extremum()
      Description copied from class: PriorityQueue
      Retrieve the Top from the Heap
      Specified by:
      extremum in class PriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
      Returns:
      The Top Key in the Heap

    • extractExtremum

      public PriorityQueueEntry<KEY,​ITEM> extractExtremum()
      Description copied from class: PriorityQueue
      Extract the Top from the Heap
      Specified by:
      extractExtremum in class PriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
      Returns:
      The Top Key in the Heap

    • impliedErrorRate

      public double impliedErrorRate()
      Compute the Implied Error Rate
      Returns:
      The Implied Error Rate

    • toString

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