Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Generic Min Priority Queue
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class MinPQ<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 MinPQ( int initCapacity )
{
pq = ( Key[] ) new Object[ initCapacity + 1 ];
n = 0;
}
public MinPQ() { this( 1 ); }
public MinPQ( int initCapacity, Comparator<Key> comparator )
{
this.comparator = comparator;
pq = ( Key[] ) new Object[ initCapacity + 1 ];
n = 0;
}
public MinPQ( Comparator<Key> comparator ) { this( 1, comparator ); }
public MinPQ( 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 isMinHeap();
}
public boolean isEmpty() { return n == 0; }
public int size() { return n; }
public Key min()
{
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 isMinHeap();
}
public Key delMin()
{
if ( isEmpty() ) throw new NoSuchElementException( "Priority queue underflow" );
Key min = pq[ 1 ];
exch( 1, n-- );
sink( 1 );
pq[ n + 1 ] = null; // to avoid loiterig and help with garbage collection
if ( ( n > 0 ) && ( n == ( pq.length - 1 ) / 4 ) ) resize( pq.length / 2 );
assert isMinHeap();
return min;
}
private void swim( int k )
{
while ( k > 1 && greater( 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 && greater( j, j + 1 ) ) j++;
if ( !greater( k, j ) ) break;
exch( k, j );
k = j;
}
}
private boolean greater( 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 isMinHeap()
{
return isMinHeap( 1 );
}
private boolean isMinHeap( int k )
{
if ( k > n ) return true;
int left = 2 * k;
int right = 2 * k + 1;
if ( left <= n && greater( k, left ) ) return false;
if ( right <= n && greater( k, right ) ) return false;
return isMinHeap( left ) && isMinHeap( right );
}
public Iterator<Key> iterator() { return new HeapIterator(); }
private class HeapIterator implements Iterator<Key>
{
private MinPQ<Key> copy;
public HeapIterator()
{
if ( comparator == null ) copy = new MinPQ<Key>( size() );
else copy = new MinPQ<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.delMin();
}
}
public static void main( String[] args )
{
MinPQ<String> pq = new MinPQ<String>();
while ( !StdIn.isEmpty() )
{
String item = StdIn.readString();
if ( !item.equals( "-" ) ) pq.insert( item );
else if ( !pq.isEmpty() ) StdOut.print( pq.delMin() + " " );
}
StdOut.println( "(" + pq.size() + " left on pq)" );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment