Package org.drip.graph.heap

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

java.lang.Object
org.drip.graph.heap.PriorityQueue<KEY,​ITEM>
org.drip.graph.heap.BinomialTreePriorityQueue<KEY,​ITEM>
public class BinomialTreePriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends PriorityQueue<KEY,​ITEM>
BinomialTreePriorityQueue implements an Binomial Tree Based Priority Queue. 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 3rd 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




Author:
Lakshmi Krishnamurthy

  • Constructor Details

    • BinomialTreePriorityQueue

      public BinomialTreePriorityQueue​(boolean minHeap)
      BinomialTreePriorityQueue Constructor
      Parameters:
      minHeap - TRUE - Indicates that Heap is a Min Heap

  • Method Details

    • binomialTreeList

      public java.util.List<BinomialTree<KEY,​ITEM>> binomialTreeList()
      Retrieve the List of Binomial Trees
      Returns:
      List of Binomial Trees

    • meld

      public boolean meld​(BinomialTree<KEY,​ITEM> tree)
      Meld the Specified Tree into the Heap
      Parameters:
      tree - The Tree to Meld
      Returns:
      TRUE - The Tree successfully melded into 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

    • 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

    • 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

    • 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

    • toString

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