Package algs24

Class MaxPQ<K extends Comparable<? super K>>

java.lang.Object

algs24.MaxPQ<K>

All Implemented Interfaces:

Iterable<K>

public class MaxPQ<K extends Comparable<? super K>>
extends Object
implements Iterable<K>

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.

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.

This implementation uses a binary heap.

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

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private class	MaxPQ.HeapIterator

Field Summary

Fields

Modifier and Type	Field	Description
private Comparator<? super K>	comparator
static boolean	DEBUG	A test client.
private int	N
private K[]	pq

Constructor Summary

Constructors

Constructor	Description
MaxPQ()	Create an empty priority queue.
MaxPQ(int initCapacity)	Create an empty priority queue with the given initial capacity.
MaxPQ(int initCapacity, Comparator<? super K> comparator)
MaxPQ(Comparator<? super K> comparator)	Create an empty priority queue using the given comparator.
MaxPQ(K[] keys)	Create a priority queue with the given items.

Method Summary

Modifier and Type	Method	Description
K	delMax()	Delete and return the largest key on the priority queue.
private void	exch(int i, int j)
void	insert(K x)	Add a new key to the priority queue.
boolean	isEmpty()	Is the priority queue empty?
private boolean	isMaxHeap()
private boolean	isMaxHeap(int k)
Iterator<K>	iterator()	Return an iterator that iterates over all of the keys on the priority queue in descending order.
private boolean	less(int i, int j)
static void	main(String[] args)
K	max()	Return the largest key on the priority queue.
private void	resize(int capacity)
(package private) void	showHeap()
private void	sink(int k)
int	size()	Return the number of items on the priority queue.
private void	swim(int k)

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

Field Details

pq

private K extends Comparable<? super K>[] pq

N

private int N

comparator

private Comparator<? super K extends Comparable<? super K>> comparator

DEBUG

public static boolean DEBUG

A test client.

Constructor Details

MaxPQ

public MaxPQ(int initCapacity,
 Comparator<? super K> comparator)

MaxPQ

public MaxPQ(int initCapacity)

Create an empty priority queue with the given initial capacity.

MaxPQ

public MaxPQ(Comparator<? super K> comparator)

Create an empty priority queue using the given comparator.

MaxPQ

public MaxPQ()

Create an empty priority queue.

MaxPQ

public MaxPQ(K[] keys)

Create a priority queue with the given items. Takes time proportional to the number of items using sink-based heap construction.

Method Details

resize

private void resize(int capacity)

isEmpty

public boolean isEmpty()

Is the priority queue empty?

size

public int size()

Return the number of items on the priority queue.

max

public K max()

Return the largest key on the priority queue.

Throws:

NoSuchElementException - if the priority queue is empty.

insert

public void insert(K x)

Add a new key to the priority queue.

delMax

public K delMax()

Delete and return the largest key on the priority queue.

Throws:

NoSuchElementException - if the priority queue is empty.

swim

private void swim(int k)

sink

private void sink(int k)

less

private boolean less(int i,
 int j)

exch

private void exch(int i,
 int j)

isMaxHeap

private boolean isMaxHeap()

isMaxHeap

private boolean isMaxHeap(int k)

iterator

public Iterator<K> iterator()

Return an iterator that iterates over all of 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<K extends Comparable<? super K>>

showHeap

void showHeap()

main

public static void main(String[] args)