Class Heap


  • public class Heap
    extends 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 Detail

      • nodes_

        protected Object[] nodes_
      • count_

        protected int count_
    • Constructor Detail

      • Heap

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

      • compare

        protected int compare​(Object a,
                              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​(Object x)
        insert an element, resize if necessary
      • extract

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

        public 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