Max Priority Queue

MaxPQ.java

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class MaxPQ<Key> implements Iterable<Key>
{
    private Key[] pq;                    // store items at indices 1 to n
    private int n;                       // number of items on priority queue
    private Comparator<Key> comparator;  // optional comparator

    public MaxPQ( int initCapacity )
    {
        pq = ( Key[] ) new Object[ initCapacity + 1 ];
        n = 0;
    }

    public MaxPQ() { this( 1 ); }

    public MaxPQ( int initCapacity, Comparator<Key> comparator )
    {
        this.comparator = comparator;
        pq = ( Key[] ) new Object[ initCapacity + 1 ];
        n = 0;
    }

    public MaxPQ( Comparator<Key> comparator )
    { this( 1, comparator ); }

    public MaxPQ( Key[] keys )
    {
        n = keys.length;
        pq = ( Key[] ) new Object[ keys.length + 1 ];

        for ( int i = 0; i < n; i++ )
            pq[ i + 1 ] = keys[ i ];

        for ( int k = n / 2; k >= 1; k-- )
            sink( k );
        assert isMaxHeap();
    }

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

    public int size() { return n; }

    public Key max()
    {
        if ( isEmpty() ) throw new NoSuchElementException("Priority queue underflow" );
        return pq[ 1 ];
    }

    private void resize( int capacity )
    {
        assert capacity > n;
        Key[] temp = ( Key[] ) new Object[ capacity ];

        for ( int i = 1; i <= n; i++ )
        {
            temp[ i ] = pq[ i ];
        }
        pq = temp;
    }

    public void insert( Key x )
    {
        if ( n == pq.length - 1 ) resize( 2 * pq.length );

        pq[ ++n ] = x;
        swim( n );
        assert isMaxHeap();
    }

    public Key delMax()
    {
        if ( isEmpty() ) throw new NoSuchElementException("Priority queue underflow" );
        Key max = pq[ 1 ];
        exch( 1, n-- );
        sink( 1 );
        pq[ n + 1 ] = null;

        if ( ( n > 0 ) && ( n == ( pq.length - 1) / 4 ) ) resize( pq.length / 2 );
        assert isMaxHeap();
        return max;
    }

    private void swim( int k )
    {
        while ( k > 1 && less( k / 2, k ) )
        {
            exch( k, k / 2 );
            k = k / 2;
        }
    }

    private void sink( int k )
    {
        while ( 2 * k <= n )
        {
            int j = 2 * k;

            if ( j < n && less( j, j + 1 ) ) j++;
            if ( !less( k, j ) ) break;
            exch( k, j );
            k = j;
        }
    }

    private boolean less( int i, int j )
    {
        if ( comparator == null )
        {
            return ( ( Comparable<Key> ) pq[ i ] ).compareTo( pq[ j ] ) < 0;
        } else {
            return comparator.compare( pq[ i ], pq[ j ] ) < 0;
        }
    }

    private void exch( int i, int j )
    {
        Key swap = pq[ i ];
        pq[ i ] = pq[ j ];
        pq[ j ] = swap;
    }

    private boolean isMaxHeap() { return isMaxHeap( 1 ); }

    private boolean isMaxHeap( int k )
    {
        if ( k > n ) return true;
        int left = 2 * k;
        int right = 2 * k + 1;

        if ( left  <= n && less( k, left ) )  return false;
        if ( right <= n && less( k, right ) ) return false;
        return isMaxHeap( left ) && isMaxHeap( right );
    }

    public Iterator<Key> iterator() { return new HeapIterator(); }

    private class HeapIterator implements Iterator<Key>
    {
        private MaxPQ<Key> copy;

        public HeapIterator()
        {
            if ( comparator == null ) copy = new MaxPQ<Key>( size() );
            else                      copy = new MaxPQ<Key>( size(), comparator );
            for ( int i = 1; i <= n; i++ )
                copy.insert( pq[ i ] );
        }

        public boolean hasNext()  { return !copy.isEmpty();                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Key next()
        {
            if ( !hasNext() ) throw new NoSuchElementException();
            return copy.delMax();
        }
    }

    public static void main( String[] args )
    {
        MaxPQ<String> pq = new MaxPQ<String>();

        while ( !StdIn.isEmpty() )
        {
            String item = StdIn.readString();
            
            if ( !item.equals( "-" ) ) pq.insert( item );
            else if ( !pq.isEmpty() ) StdOut.print( pq.delMax() + " " );
        }
        StdOut.println( "(" + pq.size() + " left on pq)" );
    }
}