MaxPQ (algorithms 4.0.2 API)

java.lang.Object
- edu.princeton.cs.algorithms.MaxPQ<Key>

All Implemented Interfaces:

Iterable<Key>
```
public class MaxPQ<Key>
extends Object
implements 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.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor and Description
`MaxPQ()` Initializes an empty priority queue.
`MaxPQ(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, 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

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`Key`	`delMax()` Removes and returns a largest key on the priority queue.
`void`	`insert(Key x)` Adds a new key to the priority queue.
`boolean`	`isEmpty()` Is the priority queue empty?
`Iterator<Key>`	`iterator()` Returns an iterator that iterates over the keys on the priority queue in descending order.
`static void`	`main(String[] args)` Unit tests the `MaxPQ` data type.
`Key`	`max()` Returns a largest 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

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 the priority queue
  - MaxPQ
```
public MaxPQ()
```
    Initializes an empty priority queue.
  - MaxPQ
```
public MaxPQ(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 the priority queue
    
    comparator - the order in which to compare the keys
  - MaxPQ
```
public MaxPQ(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()
```
    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
  - max
```
public Key max()
```
    Returns a largest key on the priority queue.
    
    Returns:
    
    a largest key on the priority queue
    
    Throws:
    
    NoSuchElementException - if the priority queue is empty
  - insert
```
public void insert(Key x)
```
    Adds a new key to the priority queue.
    
    Parameters:
    
    x - the new key to add to the priority queue
  - delMax
```
public Key delMax()
```
    Removes and returns a largest key on the priority queue.
    
    Returns:
    
    a largest key on the priority queue
    
    Throws:
    
    NoSuchElementException - if priority queue is empty.
  - iterator
```
public Iterator<Key> iterator()
```
    Returns an iterator that iterates over the keys on the priority queue in descending order. The iterator doesn't implement remove() since it's optional.
    
    Specified by:
    
    iterator in interface Iterable<Key>
    
    Returns:
    
    an iterator that iterates over the keys in descending order
  - main
```
public static void main(String[] args)
```
    Unit tests the MaxPQ data type.

Class MaxPQ<Key>

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Methods inherited from interface java.lang.Iterable

Constructor Detail

MaxPQ

MaxPQ

MaxPQ

MaxPQ

MaxPQ

Method Detail

isEmpty

size

max

insert

delMax

iterator

main