Package edu.princeton.cs.algs4

Class BinomialMinPQ<Key>

Object

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

All Implemented Interfaces:

Iterable<Key>

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

The BinomialMinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with the merging of two heaps together. 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 binomial heap. The insert, delete-the-minimum, union, min-key and size operations take logarithmic time. The is-empty and constructor operations take constant time.

Author:

Tristan Claverie

Constructor Summary

Constructors

Constructor	Description
BinomialMinPQ()	Initializes an empty priority queue Worst case is O(1)
BinomialMinPQ(Comparator<Key> C)	Initializes an empty priority queue using the given Comparator Worst case is O(1)
BinomialMinPQ(Comparator<Key> C, Key[] a)	Initializes a priority queue with given keys using the given Comparator Worst case is O(n*log(n))
BinomialMinPQ(Key[] a)	Initializes a priority queue with given keys Worst case is O(n*log(n))

Method Summary

Modifier and Type	Method	Description
Key	delMin()	Deletes the minimum key Worst case is O(log(n))
void	insert(Key key)	Puts a Key in the heap Worst case is O(log(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(log(n)) hasNext() : Worst case is O(1)
Key	minKey()	Get the minimum key currently in the queue Worst case is O(log(n))
int	size()	Number of elements currently on the priority queue Worst case is O(log(n))
BinomialMinPQ<Key>	union(BinomialMinPQ<Key> heap)	Merges two Binomial heaps together This operation is destructive Worst case is O(log(n))

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

BinomialMinPQ

public BinomialMinPQ()

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

BinomialMinPQ

public BinomialMinPQ(Comparator<Key> C)

Initializes an empty priority queue using the given Comparator Worst case is O(1)

Parameters:

C - a comparator over the keys

BinomialMinPQ

public BinomialMinPQ(Key[] a)

Initializes a priority queue with given keys Worst case is O(n*log(n))

Parameters:

a - an array of keys

BinomialMinPQ

public BinomialMinPQ(Comparator<Key> C,
                     Key[] a)

Initializes a priority queue with given keys using the given Comparator Worst case is O(n*log(n))

Parameters:

C - a comparator over the keys

a - an array of keys

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(log(n))

Returns:

the number of elements on the priority queue

Throws:

ArithmeticException - if there are more than 2^63-1 elements in the queue

insert

public void insert(Key key)

Puts a Key in the heap Worst case is O(log(n))

Parameters:

key - a Key

minKey

public Key minKey()

Get the minimum key currently in the queue Worst case is O(log(n))

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(log(n))

Returns:

the minimum key

Throws:

NoSuchElementException - if the priority queue is empty

union

public BinomialMinPQ<Key> union(BinomialMinPQ<Key> heap)

Merges two Binomial heaps together This operation is destructive Worst case is O(log(n))

Parameters:

heap - a Binomial Heap to be merged with the current heap

Returns:

the union of two heaps

Throws:

IllegalArgumentException - if the heap in parameter is null

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(log(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