public Heap() 
{
      this(null);
}

Creates a new Heap whose elements inserted implement the Comparable interface.

 public Heap(Comparator comparator) 
{
      m_comparator = comparator;
      clear();
}

Creates a new Heap whose elements are compared using the given Comparator .

 public  void clear() 
{
      m_count = 0;
      m_nodes = new Object[10];
}

Empties this heap

 protected int compare(Object o1,
    Object o2) 
{
      if (m_comparator != null)
      {
         return m_comparator.compare(o1, o2);
      }
      else
      {
         if (o1 == null)
         {
            if (o2 == null) {return 0;}
            else {return -((Comparable)o2).compareTo(o1);}
         }
         else {return ((Comparable)o1).compareTo(o2);}
      }
}

Compares the given objects using the comparator, if available, or considering them Comparable objects.

 public Object extract() 
{
      if (m_count <  1) {return null;}
      else
      {
         int length = m_nodes.length  > > 1;
         // Shrink if necessary
         if (length  > 5 && m_count <  (length  > > 1))
         {
            Object[] newNodes = new Object[length];
            System.arraycopy(m_nodes, 0, newNodes, 0, length);
            m_nodes = newNodes;
         }
         //
         int k = 0;
         Object ret = m_nodes[k];
         --m_count;
         Object last = m_nodes[m_count];
         for (;;)
         {
            int l = left(k);
            if (l  >= m_count) {break;}
            else
            {
               int r = right(k);
               int child = (r  >= m_count || compare(m_nodes[l], m_nodes[r]) <  0) ? l : r;
               if (compare(last, m_nodes[child])  > 0)
               {
                  m_nodes[k] = m_nodes[child];
                  k = child;
               }
               else {break;}
            }
         }
         m_nodes[k] = last;
         m_nodes[m_count] = null;
         return ret;
      }
}

Removes and returns the least element of this heap.

 public  void insert(Object obj) 
{
      int length = m_nodes.length;
      // Expand if necessary
      if (m_count == length)
      {
         Object[] newNodes = new Object[length + length];
         System.arraycopy(m_nodes, 0, newNodes, 0, length);
         m_nodes = newNodes;
      }
      // Be cur_slot the first unused slot index; be par_slot its parent index.
      // Start from cur_slot and walk up the tree comparing the object to 
      // insert with the object at par_slot; if it's smaller move down the object at par_slot,
      // otherwise cur_slot is the index where insert the object. If not done, 
      // shift up the tree so that now cur_slot is the old par_slot and 
      // par_slot is the parent index of the new cur_slot (so the grand-parent
      // index of the old cur_slot) and compare again.
      int k = m_count;
      while (k  > 0)
      {
         int par = parent(k);
         if (compare(obj, m_nodes[par]) <  0)
         {
            m_nodes[k] = m_nodes[par];
            k = par;
         }
         else break;
      }
      m_nodes[k] = obj;
      ++m_count;
}

Inserts the given element in this heap.

 protected int left(int index) 
{
      return index + index + 1;
}

Returns the left child index of index.

 protected int parent(int index) 
{
      return (index - 1)  > > 1;
}

Returns the parent index of index.

 public Object peek() 
{
      if (m_count <  1) {return null;}
      else {return m_nodes[0];}
}

Returns, without removing it, the least element of this heap.

 protected int right(int index) 
{
      return index + index + 2;
}

Returns the right child index of index.