Package edu.princeton.cs.algs4

Class IndexFibonacciMinPQ<Key>

Object

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

All Implemented Interfaces:

Iterable<Integer>

public class IndexFibonacciMinPQ<Key>
extends Object
implements Iterable<Integer>

Constructor Summary

Constructors

Constructor	Description
IndexFibonacciMinPQ(int N)	Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)
IndexFibonacciMinPQ(Comparator<Key> C, int N)	Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)

Method Summary

Modifier and Type	Method	Description
void	changeKey(int i, Key key)	Changes the key associated with index i to the given key If the given key is greater, Worst case is O(log(n)) If the given key is lower, Worst case is O(1) (amortized)
boolean	contains(int i)	Does the priority queue contains the index i ? Worst case is O(1)
void	decreaseKey(int i, Key key)	Decreases the key associated with index i to the given key Worst case is O(1) (amortized).
void	delete(int i)	Deletes the key associated the given index Worst case is O(log(n)) (amortized)
int	delMin()	Delete the minimum key Worst case is O(log(n)) (amortized)
void	increaseKey(int i, Key key)	Increases the key associated with index i to the given key Worst case is O(log(n))
void	insert(int i, Key key)	Associates a key with an index Worst case is O(1)
boolean	isEmpty()	Whether the priority queue is empty Worst case is O(1)
Iterator<Integer>	iterator()	Get an Iterator over the indexes 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	keyOf(int i)	Get the key associated with index i Worst case is O(1)
int	minIndex()	Get the index associated with the minimum key Worst case is O(1)
Key	minKey()	Get 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 java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

Constructor Detail

IndexFibonacciMinPQ

public IndexFibonacciMinPQ(int N)

Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)

Parameters:

N - number of keys in the priority queue, index from 0 to N-1

Throws:

IllegalArgumentException - if N < 0

IndexFibonacciMinPQ

public IndexFibonacciMinPQ(Comparator<Key> C,
                           int N)

Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)

Parameters:

N - number of keys in the priority queue, index from 0 to N-1

C - a Comparator over the keys

Throws:

IllegalArgumentException - if N < 0

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

contains

public boolean contains(int i)

Does the priority queue contains the index i ? Worst case is O(1)

Parameters:

i - an index

Returns:

true if i is on the priority queue, false if not

Throws:

IllegalArgumentException - if the specified index is invalid

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(int i,
                   Key key)

Associates a key with an index Worst case is O(1)

Parameters:

i - an index

key - a Key associated with i

Throws:

IllegalArgumentException - if the specified index is invalid

IllegalArgumentException - if the index is already in the queue

minIndex

public int minIndex()

Get the index associated with the minimum key Worst case is O(1)

Returns:

the index associated with the minimum key

Throws:

NoSuchElementException - if the priority queue is empty

minKey

public Key minKey()

Get 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 int delMin()

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

Returns:

the index associated with the minimum key

Throws:

NoSuchElementException - if the priority queue is empty

keyOf

public Key keyOf(int i)

Get the key associated with index i Worst case is O(1)

Parameters:

i - an index

Returns:

the key associated with index i

Throws:

IllegalArgumentException - if the specified index is invalid

NoSuchElementException - if the index is not in the queue

changeKey

public void changeKey(int i,
                      Key key)

Changes the key associated with index i to the given key If the given key is greater, Worst case is O(log(n)) If the given key is lower, Worst case is O(1) (amortized)

Parameters:

i - an index

key - the key to associate with i

Throws:

IllegalArgumentException - if the specified index is invalid

NoSuchElementException - if the index has no key associated with

decreaseKey

public void decreaseKey(int i,
                        Key key)

Decreases the key associated with index i to the given key Worst case is O(1) (amortized).

Parameters:

i - an index

key - the key to associate with i

Throws:

IllegalArgumentException - if the specified index is invalid

NoSuchElementException - if the index has no key associated with

IllegalArgumentException - if the given key is greater than the current key

increaseKey

public void increaseKey(int i,
                        Key key)

Increases the key associated with index i to the given key Worst case is O(log(n))

Parameters:

i - an index

key - the key to associate with i

Throws:

IllegalArgumentException - if the specified index is invalid

NoSuchElementException - if the index has no key associated with

IllegalArgumentException - if the given key is lower than the current key

delete

public void delete(int i)

Deletes the key associated the given index Worst case is O(log(n)) (amortized)

Parameters:

i - an index

Throws:

IllegalArgumentException - if the specified index is invalid

NoSuchElementException - if the given index has no key associated with

iterator

public Iterator<Integer> iterator()

Get an Iterator over the indexes 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 Iterable<Key>

Returns:

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