edu.princeton.cs.algs4

Class MultiwayMinPQ<Key>

Object

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

All Implemented Interfaces:

Iterable<Key>

public class MultiwayMinPQ<Key>
extends Object
implements Iterable<Key>

The MultiwayMinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum operations. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys. It is possible to build the priority queue using a Comparator. If not, the natural order relation between the keys will be used. This implementation uses a multiway heap. For simplified notations, logarithm in base d will be referred as log-d The delete-the-minimum operation takes time proportional to d*log-d(n) The insert takes time proportional to log-d(n) The is-empty, min-key and size operations take constant time. Constructor takes time proportional to the specified capacity.

Author:

Tristan Claverie

Constructor Summary

Constructors

Constructor and Description
MultiwayMinPQ(Comparator<Key> comparator, int d) Initializes an empty priority queue Worst case is O(d)
MultiwayMinPQ(Comparator<Key> comparator, Key[] a, int d) Initializes a priority queue with given indexes Worst case is O(a*log-d(n))
MultiwayMinPQ(int d) Initializes an empty priority queue Worst case is O(d)
MultiwayMinPQ(Key[] a, int d) Initializes a priority queue with given indexes Worst case is O(n*log-d(n))

Method Summary

Modifier and Type	Method and Description
Key	delMin() Deletes the minimum key Worst case is O(d*log-d(n))
void	insert(Key key) Puts a Key on the priority queue Worst case is O(log-d(n))
boolean	isEmpty() Whether the priority queue is empty Worst case is O(1)
Iterator<Key>	iterator() Gets an Iterator over the keys in the priority queue in ascending order The Iterator does not implement the remove() method iterator() : Worst case is O(n) next() : Worst case is O(d*log-d(n)) hasNext() : Worst case is O(1)
Key	minKey() Gets the minimum key currently in the queue Worst case is O(1)
int	size() Number of elements currently on the priority queue Worst case is O(1)

Methods inherited from class Object

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

Methods inherited from interface Iterable

forEach, spliterator

Constructor Detail

MultiwayMinPQ

public MultiwayMinPQ(int d)

Initializes an empty priority queue Worst case is O(d)

Parameters:

d - dimension of the heap

Throws:

IllegalArgumentException - if d < 2

MultiwayMinPQ

public MultiwayMinPQ(Comparator<Key> comparator,
                     int d)

Initializes an empty priority queue Worst case is O(d)

Parameters:

d - dimension of the heap

comparator - a Comparator over the keys

Throws:

IllegalArgumentException - if d < 2

MultiwayMinPQ

public MultiwayMinPQ(Key[] a,
                     int d)

Initializes a priority queue with given indexes Worst case is O(n*log-d(n))

Parameters:

d - dimension of the heap

a - an array of keys

Throws:

IllegalArgumentException - if d < 2

MultiwayMinPQ

public MultiwayMinPQ(Comparator<Key> comparator,
                     Key[] a,
                     int d)

Initializes a priority queue with given indexes Worst case is O(a*log-d(n))

Parameters:

d - dimension of the heap

comparator - a Comparator over the keys

a - an array of keys

Throws:

IllegalArgumentException - if d < 2

Method Detail

isEmpty

public boolean isEmpty()

Whether the priority queue is empty Worst case is O(1)

Returns:

true if the priority queue is empty, false if not

size

public int size()

Number of elements currently on the priority queue Worst case is O(1)

Returns:

the number of elements on the priority queue

insert

public void insert(Key key)

Puts a Key on the priority queue Worst case is O(log-d(n))

Parameters:

key - a Key

minKey

public Key minKey()

Gets the minimum key currently in the queue Worst case is O(1)

Returns:

the minimum key currently in the priority queue

Throws:

NoSuchElementException - if the priority queue is empty

delMin

public Key delMin()

Deletes the minimum key Worst case is O(d*log-d(n))

Returns:

the minimum key

Throws:

NoSuchElementException - if the priority queue is empty

iterator

public Iterator<Key> iterator()

Gets an Iterator over the keys in the priority queue in ascending order The Iterator does not implement the remove() method iterator() : Worst case is O(n) next() : Worst case is O(d*log-d(n)) hasNext() : Worst case is O(1)

Specified by:

iterator in interface Iterable<Key>

Returns:

an Iterator over the keys in the priority queue in ascending order