public BinaryHeap() 
{
  // package scoped for testing
        this(DEFAULT_CAPACITY, true);
}

Constructs a new minimum binary heap.

 public BinaryHeap(Comparator comparator) 
{
        this();
        m_comparator = comparator;
}

Constructs a new BinaryHeap that will use the given comparator to order its elements.

Parameters:

comparator - the comparator used to order the elements, null means use natural order

 public BinaryHeap(int capacity) 
{
        this(capacity, true);
}

Constructs a new minimum binary heap with the specified initial capacity.

Parameters:

capacity - The initial capacity for the heap. This value must be greater than zero.

Throws:

IllegalArgumentException - if capacity is <= 0

 public BinaryHeap(boolean isMinHeap) 
{
        this(DEFAULT_CAPACITY, isMinHeap);
}

Constructs a new minimum or maximum binary heap

Parameters:

isMinHeap - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap

 public BinaryHeap(int capacity,
    Comparator comparator) 
{
        this(capacity);
        m_comparator = comparator;
}

Constructs a new BinaryHeap.

Parameters:

capacity - the initial capacity for the heap

comparator - the comparator used to order the elements, null means use natural order

Throws:

IllegalArgumentException - if capacity is <= 0

 public BinaryHeap(boolean isMinHeap,
    Comparator comparator) 
{
        this(isMinHeap);
        m_comparator = comparator;
}

Constructs a new BinaryHeap.

Parameters:

isMinHeap - true to use the order imposed by the given comparator; false to reverse that order

comparator - the comparator used to order the elements, null means use natural order

 public BinaryHeap(int capacity,
    boolean isMinHeap) 
{
        if (capacity < = 0) {
            throw new IllegalArgumentException("invalid capacity");
        }
        m_isMinHeap = isMinHeap;
        //+1 as 0 is noop
        m_elements = new Object[capacity + 1];
}

Constructs a new minimum or maximum binary heap with the specified initial capacity.

Parameters:

capacity - the initial capacity for the heap. This value must be greater than zero.

isMinHeap - if true the heap is created as a minimum heap; otherwise, the heap is created as a maximum heap.

Throws:

IllegalArgumentException - if capacity is <= 0

 public BinaryHeap(int capacity,
    boolean isMinHeap,
    Comparator comparator) 
{
        this(capacity, isMinHeap);
        m_comparator = comparator;
}

Constructs a new BinaryHeap.

Parameters:

capacity - the initial capacity for the heap

isMinHeap - true to use the order imposed by the given comparator; false to reverse that order

comparator - the comparator used to order the elements, null means use natural order

Throws:

IllegalArgumentException - if capacity is <= 0

 public boolean add(Object object) 
{
        insert(object);
        return true;
}

Adds an object to this heap. Same as #insert(Object) .

 public  void clear() 
{
        m_elements = new Object[m_elements.length];  // for gc
        m_size = 0;
}

Clears all elements from queue.

 public Object get() 
{
        try {
            return peek();
        } catch (NoSuchElementException e) {
            throw new BufferUnderflowException();
        }
}

Returns the priority element. Same as #peek() .

 protected  void grow() 
{
        final Object[] elements = new Object[m_elements.length * 2];
        System.arraycopy(m_elements, 0, elements, 0, m_elements.length);
        m_elements = elements;
}

Increases the size of the heap to support additional elements

 public  void insert(Object element) 
{
        if (isFull()) {
            grow();
        }
        //percolate element to it's place in tree
        if (m_isMinHeap) {
            percolateUpMinHeap(element);
        } else {
            percolateUpMaxHeap(element);
        }
}

Inserts an element into queue.

 public boolean isEmpty() 
{
        return m_size == 0;
}

Tests if queue is empty.

 public boolean isFull() 
{
        //+1 as element 0 is noop
        return m_elements.length == m_size + 1;
}

Tests if queue is full.

 public Iterator iterator() 
{
        return new Iterator() {
            private int index = 1;
            private int lastReturnedIndex = -1;
            public boolean hasNext() {
                return index < = m_size;
            }
            public Object next() {
                if (!hasNext()) throw new NoSuchElementException();
                lastReturnedIndex = index;
                index++;
                return m_elements[lastReturnedIndex];
            }
            public void remove() {
                if (lastReturnedIndex == -1) {
                    throw new IllegalStateException();
                }
                m_elements[ lastReturnedIndex ] = m_elements[ m_size ];
                m_elements[ m_size ] = null;
                m_size--;  
                if( m_size != 0 && lastReturnedIndex < = m_size) {
                    int compareToParent = 0;
                    if (lastReturnedIndex  > 1) {
                        compareToParent = compare(m_elements[lastReturnedIndex], 
                            m_elements[lastReturnedIndex / 2]);  
                    }
                    if (m_isMinHeap) {
                        if (lastReturnedIndex  > 1 && compareToParent <  0) {
                            percolateUpMinHeap(lastReturnedIndex); 
                        } else {
                            percolateDownMinHeap(lastReturnedIndex);
                        }
                    } else {  // max heap
                        if (lastReturnedIndex  > 1 && compareToParent  > 0) {
                            percolateUpMaxHeap(lastReturnedIndex); 
                        } else {
                            percolateDownMaxHeap(lastReturnedIndex);
                        }
                    }          
                }
                index--;
                lastReturnedIndex = -1; 
            }
        };
}

Returns an iterator over this heap's elements.

 public Object peek() throws NoSuchElementException 
{
        if (isEmpty()) {
            throw new NoSuchElementException();
        } else {
            return m_elements[1];
        }
}

Returns the element on top of heap but don't remove it.

 protected  void percolateDownMaxHeap(int index) 
{
        final Object element = m_elements[index];
        int hole = index;
        while ((hole * 2) < = m_size) {
            int child = hole * 2;
            // if we have a right child and that child can not be percolated
            // up then move onto other child
            if (child != m_size && compare(m_elements[child + 1], m_elements[child])  > 0) {
                child++;
            }
            // if we found resting place of bubble then terminate search
            if (compare(m_elements[child], element) < = 0) {
                break;
            }
            m_elements[hole] = m_elements[child];
            hole = child;
        }
        m_elements[hole] = element;
}

Percolates element down heap from the position given by the index.

Assumes it is a maximum heap.

 protected  void percolateDownMinHeap(int index) 
{
        final Object element = m_elements[index];
        int hole = index;
        while ((hole * 2) < = m_size) {
            int child = hole * 2;
            // if we have a right child and that child can not be percolated
            // up then move onto other child
            if (child != m_size && compare(m_elements[child + 1], m_elements[child]) <  0) {
                child++;
            }
            // if we found resting place of bubble then terminate search
            if (compare(m_elements[child], element)  >= 0) {
                break;
            }
            m_elements[hole] = m_elements[child];
            hole = child;
        }
        m_elements[hole] = element;
}

Percolates element down heap from the position given by the index.

Assumes it is a minimum heap.

 protected  void percolateUpMaxHeap(int index) 
{
        int hole = index;
        Object element = m_elements[hole];
        while (hole  > 1 && compare(element, m_elements[hole / 2])  > 0) {
            // save element that is being pushed down
            // as the element "bubble" is percolated up
            final int next = hole / 2;
            m_elements[hole] = m_elements[next];
            hole = next;
        }
        m_elements[hole] = element;
}

Percolates element up heap from from the position given by the index.

Assume it is a maximum heap.

 protected  void percolateUpMaxHeap(Object element) 
{
        m_elements[++m_size] = element;
        percolateUpMaxHeap(m_size);
}

Percolates a new element up heap from the bottom.

Assume it is a maximum heap.

 protected  void percolateUpMinHeap(int index) 
{
        int hole = index;
        Object element = m_elements[hole];
        while (hole  > 1 && compare(element, m_elements[hole / 2]) <  0) {
            // save element that is being pushed down
            // as the element "bubble" is percolated up
            final int next = hole / 2;
            m_elements[hole] = m_elements[next];
            hole = next;
        }
        m_elements[hole] = element;
}

Percolates element up heap from the position given by the index.

Assumes it is a minimum heap.

 protected  void percolateUpMinHeap(Object element) 
{
        m_elements[++m_size] = element;
        percolateUpMinHeap(m_size);
}

Percolates a new element up heap from the bottom.

Assumes it is a minimum heap.

 public Object pop() throws NoSuchElementException 
{
        final Object result = peek();
        m_elements[1] = m_elements[m_size--];
        // set the unused element to 'null' so that the garbage collector
        // can free the object if not used anywhere else.(remove reference)
        m_elements[m_size + 1] = null;
        if (m_size != 0) {
            // percolate top element to it's place in tree
            if (m_isMinHeap) {
                percolateDownMinHeap(1);
            } else {
                percolateDownMaxHeap(1);
            }
        }
        return result;
}

Returns the element on top of heap and remove it.

 public Object remove() 
{
        try {
            return pop();
        } catch (NoSuchElementException e) {
            throw new BufferUnderflowException();
        }
}

Removes the priority element. Same as #pop() .

 public int size() 
{
        return m_size;
}

Returns the number of elements in this heap.

 public String toString() 
{
        final StringBuffer sb = new StringBuffer();
        sb.append("[ ");
        for (int i = 1; i <  m_size + 1; i++) {
            if (i != 1) {
                sb.append(", ");
            }
            sb.append(m_elements[i]);
        }
        sb.append(" ]");
        return sb.toString();
}

Returns a string representation of this heap. The returned string is similar to those produced by standard JDK collections.