Package org.drip.graph.heap

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

java.lang.Object
org.drip.graph.heap.PriorityQueue<KEY,​ITEM>
Direct Known Subclasses:
ApproximatePriorityQueue, BinaryTreePriorityQueue, BinomialTreePriorityQueue, KaplanZwickPriorityQueue
public abstract class PriorityQueue<KEY extends java.lang.Comparable<KEY>,​ITEM>
extends java.lang.Object
PriorityQueue exposes the Stubs of a Priority Queue's Operations. The References are:

  • Brodal, G. S. (1996): Priority Queue on Parallel Machines Scandinavian Workshop on Algorithm Theory – SWAT ’96 416-427
  • Cormen, T., C. E. Leiserson, R. Rivest, and C. Stein (2009): Introduction to Algorithms 3rd Edition MIT Press
  • Sanders, P., K. Mehlhorn, M. Dietzfelbinger, and R. Dementiev (2019): Sequential and Parallel Algorithms and Data Structures – A Basic Toolbox Springer
  • Sundell, H., and P. Tsigas (2005): Fast and Lock-free Concurrent Priority Queues for Multi-threaded Systems Journal of Parallel and Distributed Computing 65 (5) 609-627
  • Wikipedia (2020): Priority Queue https://en.wikipedia.org/wiki/Priority_queue




Author:
Lakshmi Krishnamurthy

  • Constructor Summary

    Constructors
    Constructor Description
    PriorityQueue​(boolean minHeap)
    PriorityQueue Constructor

  • Method Summary

    Modifier and Type Method Description
    boolean delete​(KEY key)
    Delete the Entry corresponding to the specified Key
    abstract PriorityQueueEntry<KEY,​ITEM> extractExtremum()
    Extract the Top from the Heap
    abstract PriorityQueueEntry<KEY,​ITEM> extremum()
    Retrieve the Top from the Heap
    abstract boolean insert​(KEY key, ITEM item)
    Insert the Specified Key/Item into the Heap
    abstract boolean isEmpty()
    Indicate if the Heap is Empty
    abstract boolean meld​(PriorityQueue<KEY,​ITEM> priorityQueueOther)
    Meld the Specified Priority Queue with the Current
    boolean minHeap()
    Indicate if the Binary Heap is a Min Heap
    java.util.List<PriorityQueueEntry<KEY,​ITEM>> sortedEntryList()
    Generate the Sorted Entry List
    java.util.List<ITEM> sortedItemList()
    Generate the Sorted Item List
    java.util.List<KEY> sortedKeyList()
    Generate the Sorted Key List

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • PriorityQueue

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

  • Method Details

    • minHeap

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

    • insert

      public abstract boolean insert​(KEY key, ITEM item)
      Insert the Specified Key/Item into the Heap
      Parameters:
      key - Key
      item - Node Item
      Returns:
      TRUE - The Key/Item successfully inserted

    • meld

      public abstract boolean meld​(PriorityQueue<KEY,​ITEM> priorityQueueOther)
      Meld the Specified Priority Queue with the Current
      Parameters:
      priorityQueueOther - The Specified Binary Tree Priority Queue
      Returns:
      TRUE - The Specified Priority Queue successfully melded

    • extremum

      public abstract PriorityQueueEntry<KEY,​ITEM> extremum()
      Retrieve the Top from the Heap
      Returns:
      The Top Key in the Heap

    • extractExtremum

      public abstract PriorityQueueEntry<KEY,​ITEM> extractExtremum()
      Extract the Top from the Heap
      Returns:
      The Top Key in the Heap

    • isEmpty

      public abstract boolean isEmpty()
      Indicate if the Heap is Empty
      Returns:
      TRUE - The Heap is Empty

    • delete

      public boolean delete​(KEY key)
      Delete the Entry corresponding to the specified Key
      Parameters:
      key - Key
      Returns:
      TRUE - The corresponding Entry successfully deleted

    • sortedKeyList

      public java.util.List<KEY> sortedKeyList()
      Generate the Sorted Key List
      Returns:
      The Sorted Key List

    • sortedEntryList

      public java.util.List<PriorityQueueEntry<KEY,​ITEM>> sortedEntryList()
      Generate the Sorted Entry List
      Returns:
      The Sorted Entry List

    • sortedItemList

      public java.util.List<ITEM> sortedItemList()
      Generate the Sorted Item List
      Returns:
      The Sorted Item List