Package algs24

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

java.lang.Object

algs24.MinPQ<K>

All Implemented Interfaces:

Iterable<K>

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

The MinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum 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-minimum operations take logarithmic amortized time. The min, 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.

Field Summary

Fields

Modifier and Type	Field	Description
static boolean	DEBUG	A test client.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method	Description
K	delMin()	Delete and return the smallest key on the priority queue.
void	insert(K x)	Add a new key to the priority queue.
boolean	isEmpty()	Is the priority queue empty?
Iterator<K>	iterator()	Return an iterator that iterates over all of the keys on the priority queue in ascending order.
static void	main(String[] args)
K	min()	Return the smallest key on the priority queue.
int	size()	Return the number of items on the 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

Field Details

DEBUG

public static boolean DEBUG

A test client.

Constructor Details

MinPQ

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

MinPQ

public MinPQ(int initCapacity)

Create an empty priority queue with the given initial capacity.

MinPQ

public MinPQ(Comparator<? super K> comparator)

Create an empty priority queue using the given comparator.

MinPQ

public MinPQ()

Create an empty priority queue.

MinPQ

public MinPQ(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

isEmpty

public boolean isEmpty()

Is the priority queue empty?

size

public int size()

Return the number of items on the priority queue.

min

public K min()

Return the smallest 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.

delMin

public K delMin()

Delete and return the smallest key on the priority queue.

Throws:

NoSuchElementException - if the priority queue is empty.

iterator

public Iterator<K> iterator()

Return an iterator that iterates over all of the keys on the priority queue in ascending order.

The iterator doesn't implement remove() since it's optional.

Specified by:

iterator in interface Iterable<K extends Comparable<? super K>>

main

public static void main(String[] args)