Package edu.princeton.cs.algs4
Class MinPQ<Key>
 Object

 edu.princeton.cs.algs4.MinPQ<Key>

 Type Parameters:
Key
 the generic type of key on this priority queue
 All Implemented Interfaces:
Iterable<Key>
public class MinPQ<Key> extends Object implements Iterable<Key>
TheMinPQ
class represents a priority queue of generic keys. It supports the usual insert and deletetheminimum 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 deletetheminimum operations take Θ(log n) amortized time, where n is the number of elements in the priority queue. This is an amortized bound (and not a worstcase bound) because of array resizing operations. The min, size, and isempty operations take Θ(1) time in the worst case. 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.
 Author:
 Robert Sedgewick, Kevin Wayne


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

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Key
delMin()
Removes and returns a smallest key on this priority queue.void
insert(Key x)
Adds a new key to this priority queue.boolean
isEmpty()
Returns true if this priority queue is empty.Iterator<Key>
iterator()
Returns an iterator that iterates over the keys on this priority queue in ascending order.static void
main(String[] args)
Unit tests theMinPQ
data type.Key
min()
Returns a smallest key on this priority queue.int
size()
Returns the number of keys on this priority queue.
Methods inherited from class java.lang.Object
clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.lang.Iterable
forEach, spliterator




Constructor Detail

MinPQ
public MinPQ(int initCapacity)
Initializes an empty priority queue with the given initial capacity. Parameters:
initCapacity
 the initial capacity of this priority queue

MinPQ
public MinPQ()
Initializes an empty priority queue.

MinPQ
public MinPQ(int initCapacity, Comparator<Key> comparator)
Initializes an empty priority queue with the given initial capacity, using the given comparator. Parameters:
initCapacity
 the initial capacity of this priority queuecomparator
 the order in which to compare the keys

MinPQ
public MinPQ(Comparator<Key> comparator)
Initializes an empty priority queue using the given comparator. Parameters:
comparator
 the order in which to compare the keys

MinPQ
public MinPQ(Key[] keys)
Initializes a priority queue from the array of keys.Takes time proportional to the number of keys, using sinkbased heap construction.
 Parameters:
keys
 the array of keys


Method Detail

isEmpty
public boolean isEmpty()
Returns true if this priority queue is empty. Returns:
true
if this priority queue is empty;false
otherwise

size
public int size()
Returns the number of keys on this priority queue. Returns:
 the number of keys on this priority queue

min
public Key min()
Returns a smallest key on this priority queue. Returns:
 a smallest key on this priority queue
 Throws:
NoSuchElementException
 if this priority queue is empty

insert
public void insert(Key x)
Adds a new key to this priority queue. Parameters:
x
 the key to add to this priority queue

delMin
public Key delMin()
Removes and returns a smallest key on this priority queue. Returns:
 a smallest key on this priority queue
 Throws:
NoSuchElementException
 if this priority queue is empty

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

main
public static void main(String[] args)
Unit tests theMinPQ
data type. Parameters:
args
 the commandline arguments

