binaryheap.java

初级java程序员如果想要更深一步提高自己的实力

     *
     * @param index the index for the element
     */
    protected void percolateDownMinHeap(final 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.
     * <p>
     * Assumes it is a maximum heap.
     *
     * @param index the index of the element
     */
    protected void percolateDownMaxHeap(final 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 up heap from the position given by the index.
     * <p>
     * Assumes it is a minimum heap.
     *
     * @param index the index of the element to be percolated up
     */
    protected void percolateUpMinHeap(final 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 a new element up heap from the bottom.
     * <p>
     * Assumes it is a minimum heap.
     *
     * @param element the element
     */
    protected void percolateUpMinHeap(final Object element) {
        m_elements[++m_size] = element;
        percolateUpMinHeap(m_size);
    }

    /**
     * Percolates element up heap from from the position given by the index.
     * <p>
     * Assume it is a maximum heap.
     *
     * @param index the index of the element to be percolated up
     */
    protected void percolateUpMaxHeap(final 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 a new element up heap from the bottom.
     * <p>
     * Assume it is a maximum heap.
     *
     * @param element the element
     */
    protected void percolateUpMaxHeap(final Object element) {
        m_elements[++m_size] = element;
        percolateUpMaxHeap(m_size);
    }
    
    /**
     * Compares two objects using the comparator if specified, or the
     * natural order otherwise.
     * 
     * @param a  the first object
     * @param b  the second object
     * @return -ve if a less than b, 0 if they are equal, +ve if a greater than b
     */
    private int compare(Object a, Object b) {
        if (m_comparator != null) {
            return m_comparator.compare(a, b);
        } else {
            return ((Comparable) a).compareTo(b);
        }
    }

    /**
     * Increases the size of the heap to support additional elements
     */
    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;
    }

    /**
     * Returns a string representation of this heap.  The returned string
     * is similar to those produced by standard JDK collections.
     *
     * @return a string representation of 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 an iterator over this heap's elements.
     *
     * @return an iterator over this heap's elements
     */
    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; 
            }

        };
    }


    /**
     * Adds an object to this heap. Same as {@link #insert(Object)}.
     *
     * @param object  the object to add
     * @return true, always
     */
    public boolean add(Object object) {
        insert(object);
        return true;
    }

    /**
     * Returns the priority element. Same as {@link #peek()}.
     *
     * @return the priority element
     * @throws BufferUnderflowException if this heap is empty
     */
    public Object get() {
        try {
            return peek();
        } catch (NoSuchElementException e) {
            throw new BufferUnderflowException();
        }
    }

    /**
     * Removes the priority element. Same as {@link #pop()}.
     *
     * @return the removed priority element
     * @throws BufferUnderflowException if this heap is empty
     */
    public Object remove() {
        try {
            return pop();
        } catch (NoSuchElementException e) {
            throw new BufferUnderflowException();
        }
    }

    /**
     * Returns the number of elements in this heap.
     *
     * @return the number of elements in this heap
     */
    public int size() {
        return m_size;
    }

}