Class Heap


  • public class Heap
    extends java.lang.Object
    A heap-based priority queue, without any concurrency control (i.e., no blocking on empty/full states). This class provides the data structure mechanics for BoundedPriorityQueue.

    The class currently uses a standard array-based heap, as described in, for example, Sedgewick's Algorithms text. All methods are fully synchronized. In the future, it may instead use structures permitting finer-grained locking.

    [ Introduction to this package. ]

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected java.util.Comparator cmp_  
      protected int count_  
      protected java.lang.Object[] nodes_  
    • Constructor Summary

      Constructors 
      Constructor Description
      Heap​(int capacity)
      Create a Heap with the given capacity, and relying on natural ordering.
      Heap​(int capacity, java.util.Comparator cmp)
      Create a Heap with the given initial capacity and comparator
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void clear()
      remove all elements
      protected int compare​(java.lang.Object a, java.lang.Object b)
      perform element comaprisons using comparator or natural ordering
      java.lang.Object extract()
      Return and remove least element, or null if empty
      void insert​(java.lang.Object x)
      insert an element, resize if necessary
      protected int left​(int k)  
      protected int parent​(int k)  
      java.lang.Object peek()
      Return least element without removing it, or null if empty
      protected int right​(int k)  
      int size()
      Return number of elements
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • nodes_

        protected java.lang.Object[] nodes_
      • count_

        protected int count_
      • cmp_

        protected final java.util.Comparator cmp_
    • Constructor Detail

      • Heap

        public Heap​(int capacity,
                    java.util.Comparator cmp)
             throws java.lang.IllegalArgumentException
        Create a Heap with the given initial capacity and comparator
        Throws:
        java.lang.IllegalArgumentException - if capacity less or equal to zero
      • Heap

        public Heap​(int capacity)
        Create a Heap with the given capacity, and relying on natural ordering.
    • Method Detail

      • compare

        protected int compare​(java.lang.Object a,
                              java.lang.Object b)
        perform element comaprisons using comparator or natural ordering
      • parent

        protected final int parent​(int k)
      • left

        protected final int left​(int k)
      • right

        protected final int right​(int k)
      • insert

        public void insert​(java.lang.Object x)
        insert an element, resize if necessary
      • extract

        public java.lang.Object extract()
        Return and remove least element, or null if empty
      • peek

        public java.lang.Object peek()
        Return least element without removing it, or null if empty
      • size

        public int size()
        Return number of elements
      • clear

        public void clear()
        remove all elements