Class Heap

java.lang.Object
EDU.oswego.cs.dl.util.concurrent.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 Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final Comparator
     
    protected int
     
    protected Object[]
     
  • Constructor Summary

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

    Modifier and Type
    Method
    Description
    void
    remove all elements
    protected int
    perform element comaprisons using comparator or natural ordering
    Return and remove least element, or null if empty
    void
    insert an element, resize if necessary
    protected final int
    left(int k)
     
    protected final int
    parent(int k)
     
    Return least element without removing it, or null if empty
    protected final int
    right(int k)
     
    int
    Return number of elements

    Methods inherited from class java.lang.Object

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

    • nodes_

      protected Object[] nodes_
    • count_

      protected int count_
    • cmp_

      protected final Comparator cmp_
  • Constructor Details

    • Heap

      public Heap(int capacity, Comparator cmp) throws IllegalArgumentException
      Create a Heap with the given initial capacity and comparator
      Throws:
      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 Details

    • 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