edu.princeton.cs.algs4

Class MaxPQ<Key>

java.lang.Object

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

Type Parameters:

Key - the generic type of key on this priority queue

All Implemented Interfaces:

java.lang.Iterable<Key>

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

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

This implementation uses a binary heap. The insert and delete-the-maximum operations take logarithmic amortized time. The max, 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
MaxPQ() Initializes an empty priority queue.
MaxPQ(java.util.Comparator<Key> comparator) Initializes an empty priority queue using the given comparator.
MaxPQ(int initCapacity) Initializes an empty priority queue with the given initial capacity.
MaxPQ(int initCapacity, java.util.Comparator<Key> comparator) Initializes an empty priority queue with the given initial capacity, using the given comparator.
MaxPQ(Key[] keys) Initializes a priority queue from the array of keys.

Method Summary

Modifier and Type	Method and Description
Key	delMax() Removes and returns a largest 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.
java.util.Iterator<Key>	iterator() Returns an iterator that iterates over the keys on this priority queue in descending order.
static void	main(java.lang.String[] args) Unit tests the MaxPQ data type.
Key	max() Returns a largest key on this priority queue.
int	size() Returns the number of keys on this priority queue.

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

MaxPQ

public MaxPQ(int initCapacity)

Initializes an empty priority queue with the given initial capacity.

Parameters:

initCapacity - the initial capacity of this priority queue

MaxPQ

public MaxPQ()

Initializes an empty priority queue.

MaxPQ

public MaxPQ(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 this priority queue

comparator - the order in which to compare the keys

MaxPQ

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

Initializes an empty priority queue using the given comparator.

Parameters:

comparator - the order in which to compare the keys

MaxPQ

public MaxPQ(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()

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

max

public Key max()

Returns a largest key on this priority queue.

Returns:

a largest key on this priority queue

Throws:

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

insert

public void insert(Key x)

Adds a new key to this priority queue.

Parameters:

x - the new key to add to this priority queue

delMax

public Key delMax()

Removes and returns a largest key on this priority queue.

Returns:

a largest key on this priority queue

Throws:

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

iterator

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

Returns an iterator that iterates over the keys on this priority queue in descending 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 descending order

main

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

Unit tests the MaxPQ data type.

Parameters:

args - the command-line arguments