Class MinPQ<Key>

java.lang.Object

MinPQ<Key>

All Implemented Interfaces:

java.lang.Iterable<Key>

public class MinPQ<Key>
extends java.lang.Object
implements java.lang.Iterable<Key>

The MinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys.

This implementation uses a binary heap. The insert and delete-the-minimum operations take logarithmic amortized time. The min, size, and is-empty operations take constant time. Construction takes time proportional to the specified capacity or the number of items used to initialize the data structure.

For additional documentation, see Section 2.4 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
MinPQ() Initializes an empty priority queue.
MinPQ(java.util.Comparator<Key> comparator) Initializes an empty priority queue using the given comparator.
MinPQ(int initCapacity) Initializes an empty priority queue with the given initial capacity.
MinPQ(int initCapacity, java.util.Comparator<Key> comparator) Initializes an empty priority queue with the given initial capacity, using the given comparator.
MinPQ(Key[] keys) Initializes a priority queue from the array of keys.

Method Summary

Methods

Modifier and Type	Method and Description
Key	delMin() Removes and returns a smallest key on the priority queue.
void	insert(Key x) Adds a new key to the priority queue.
boolean	isEmpty() Is the priority queue empty?
java.util.Iterator<Key>	iterator() Returns an iterator that iterates over the keys on the priority queue in ascending order.
static void	main(java.lang.String[] args) Unit tests the MinPQ data type.
Key	min() Returns a smallest key on the priority queue.
int	size() Returns the number of keys on the priority queue.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MinPQ

public MinPQ(int initCapacity)

Initializes an empty priority queue with the given initial capacity.

Parameters:

initCapacity - the initial capacity of the priority queue

MinPQ

public MinPQ()

Initializes an empty priority queue.

MinPQ

public MinPQ(int initCapacity,
     java.util.Comparator<Key> comparator)

Initializes an empty priority queue with the given initial capacity, using the given comparator.

Parameters:

initCapacity - the initial capacity of the priority queue

comparator - the order to use when comparing keys

MinPQ

public MinPQ(java.util.Comparator<Key> comparator)

Initializes an empty priority queue using the given comparator.

Parameters:

comparator - the order to use when comparing keys

MinPQ

public MinPQ(Key[] keys)

Initializes a priority queue from the array of keys. Takes time proportional to the number of keys, using sink-based heap construction.

Parameters:

keys - the array of keys

Method Detail

isEmpty

public boolean isEmpty()

Is the priority queue empty?

Returns:

true if the priority queue is empty; false otherwise

size

public int size()

Returns the number of keys on the priority queue.

Returns:

the number of keys on the priority queue

min

public Key min()

Returns a smallest key on the priority queue.

Returns:

a smallest key on the priority queue

Throws:

java.util.NoSuchElementException - if priority queue is empty

insert

public void insert(Key x)

Adds a new key to the priority queue.

Parameters:

x - the key to add to the priority queue

delMin

public Key delMin()

Removes and returns a smallest key on the priority queue.

Returns:

a smallest key on the priority queue

Throws:

java.util.NoSuchElementException - if the priority queue is empty

iterator

public java.util.Iterator<Key> iterator()

Returns an iterator that iterates over the keys on the priority queue in ascending order. The iterator doesn't implement remove() since it's optional.

Specified by:

iterator in interface java.lang.Iterable<Key>

Returns:

an iterator that iterates over the keys in ascending order

main

public static void main(java.lang.String[] args)

Unit tests the MinPQ data type.