public class MaxPQ<Key> extends java.lang.Object implements java.lang.Iterable<Key>
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 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.
|
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?
|
java.util.Iterator<Key> |
iterator()
Returns an iterator that iterates over the keys on the 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 the priority queue.
|
int |
size()
Returns the number of keys on the priority queue.
|
public MaxPQ(int initCapacity)
initCapacity
- the initial capacity of the priority queuepublic MaxPQ()
public MaxPQ(int initCapacity, java.util.Comparator<Key> comparator)
initCapacity
- the initial capacity of the priority queuecomparator
- the order in which to compare the keyspublic MaxPQ(java.util.Comparator<Key> comparator)
comparator
- the order in which to compare the keyspublic MaxPQ(Key[] keys)
keys
- the array of keyspublic boolean isEmpty()
public int size()
public Key max()
java.util.NoSuchElementException
- if the priority queue is emptypublic void insert(Key x)
x
- the new key to add to the priority queuepublic Key delMax()
java.util.NoSuchElementException
- if priority queue is empty.public java.util.Iterator<Key> iterator()
iterator
in interface java.lang.Iterable<Key>
public static void main(java.lang.String[] args)