Package org.drip.graph.heap

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

java.lang.Object
org.drip.graph.heap.PriorityQueue<KEY,​ITEM>
org.drip.graph.heap.BinaryTreePriorityQueue<KEY,​ITEM>
public class BinaryTreePriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends PriorityQueue<KEY,​ITEM>
BinaryTreePriorityQueue implements a Binary Heap Based off of a Binary Tree. The References are:

  • Brodal, G. S., G. Lagogiannis, and R. E. Tarjan (2012): Strict Fibonacci Heaps Proceedings on the 44th Symposium on the Theory of Computing - STOC '12 1177-1184
  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press
  • Hayward, R., and C. McDiarmid (1991): Average Case Analysis of Heap-building by Repeated Insertion Journal of Algorithms 12 (1) 126-153
  • Suchanek, M. A. (2012): Elementary yet Precise Worst-case Analysis of Floyd's Heap Construction Program Fundamenta Informaticae 120 (1) 75-92
  • Wikipedia (2020): Binary Heap https://en.wikipedia.org/wiki/Binary_heap




Author:
Lakshmi Krishnamurthy

  • Constructor Details

    • BinaryTreePriorityQueue

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

  • Method Details

    • top

      public BinaryTreeNode<KEY,​ITEM> top()
      Retrieve the Top Node
      Returns:
      The Top Node

    • maintainHeapPropertyBottomUp

      public boolean maintainHeapPropertyBottomUp​(BinaryTreeNode<KEY,​ITEM> node)
      Maintain the Binary Heap Property from the Node to the Top
      Parameters:
      node - Specified Node
      Returns:
      TRUE - The Heap Property is successfully maintained

    • maintainHeapPropertyTopDown

      public boolean maintainHeapPropertyTopDown​(BinaryTreeNode<KEY,​ITEM> node)
      Maintain the Binary Heap Property from the Node to the Bottom
      Parameters:
      node - Specified Node
      Returns:
      TRUE - The Heap Property is successfully maintained

    • 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

    • 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

    • bfsWalk

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

    • bfsLevelListMap

      public java.util.Map<java.lang.Integer,​java.util.List<BinaryTreeNode<KEY,​ITEM>>> bfsLevelListMap()
      Perform a BFS Walk and generate the Level List Map
      Returns:
      The Level List Map

    • 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

    • keyEntry

      public BinaryTreeNode<KEY,​ITEM> keyEntry​(KEY key)
      Retrieve the Node with a Key Corresponding to the Input
      Parameters:
      key - The Input Key
      Returns:
      TRUE - The Node with a Key Corresponding to the Input