edu.princeton.cs.algs4

Class FibonacciMinPQ<Key>

java.lang.Object

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

All Implemented Interfaces:

java.lang.Iterable<Key>

public class FibonacciMinPQ<Key>
extends java.lang.Object
implements java.lang.Iterable<Key>

Constructor Summary

Constructors

Constructor and Description
FibonacciMinPQ() Initializes an empty priority queue Worst case is O(1)
FibonacciMinPQ(java.util.Comparator<Key> C) Initializes an empty priority queue Worst case is O(1)
FibonacciMinPQ(java.util.Comparator<Key> C, Key[] a) Initializes a priority queue with given keys Worst case is O(n)
FibonacciMinPQ(Key[] a) Initializes a priority queue with given keys Worst case is O(n)

Method Summary

Modifier and Type	Method and Description
Key	delMin() Deletes the minimum key Worst case is O(log(n)) (amortized)
void	insert(Key key) Insert a key in the queue Worst case is O(1)
boolean	isEmpty() Whether the priority queue is empty Worst case is O(1)
java.util.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)) (amortized) 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)
FibonacciMinPQ<Key>	union(FibonacciMinPQ<Key> that) Merges two heaps together This operation is destructive Worst case is O(1)

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

Constructor Detail

FibonacciMinPQ

public FibonacciMinPQ(java.util.Comparator<Key> C)

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

Parameters:

C - a Comparator over the Keys

FibonacciMinPQ

public FibonacciMinPQ()

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

FibonacciMinPQ

public FibonacciMinPQ(Key[] a)

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

Parameters:

a - an array of keys

FibonacciMinPQ

public FibonacciMinPQ(java.util.Comparator<Key> C,
                      Key[] a)

Initializes a priority queue with given keys Worst case is O(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(1)

Returns:

the number of elements on the priority queue

insert

public void insert(Key key)

Insert a key in the queue Worst case is O(1)

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:

java.util.NoSuchElementException - if the priority queue is empty

delMin

public Key delMin()

Deletes the minimum key Worst case is O(log(n)) (amortized)

Returns:

the minimum key

Throws:

java.util.NoSuchElementException - if the priority queue is empty

union

public FibonacciMinPQ<Key> union(FibonacciMinPQ<Key> that)

Merges two heaps together This operation is destructive Worst case is O(1)

Parameters:

that - a Fibonacci heap

Returns:

the union of the two heaps

iterator

public java.util.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)) (amortized) hasNext() : Worst case is O(1)

Specified by:

iterator in interface java.lang.Iterable<Key>

Returns:

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