程序包 edu.princeton.cs.algs4

类 IndexMultiwayMinPQ<Key>

java.lang.Object

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

所有已实现的接口:

java.lang.Iterable<java.lang.Integer>

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

The IndexMultiwayMinPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with delete and change-the-key methods. In order to let the client refer to keys on the priority queue, an integer between 0 and N-1 is associated with each key ; the client uses this integer to specify which key to delete or change. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys. This implementation uses a multiway heap along with an array to associate keys with integers in the given range. For simplified notations, logarithm in base d will be referred as log-d The delete-the-minimum, delete, change-key and increase-key operations take time proportional to d*log-d(n) The insert and decrease-key take time proportional to log-d(n) The is-empty, min-index, min-key, size, contains and key-of operations take constant time. Construction takes time proportional to the specified capacity. The arrays used in this structure have the first d indices empty, it apparently helps with caching effects.

构造器概要

构造器

构造器	说明
IndexMultiwayMinPQ(int N, int D)	Initializes an empty indexed priority queue with indices between 0 to N-1 Worst case is O(n)
IndexMultiwayMinPQ(int N, java.util.Comparator<Key> C, int D)	Initializes an empty indexed priority queue with indices between 0 to N-1 Worst case is O(n)

方法概要

修饰符和类型	方法	说明
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(d*log-d(n)) If the given key is lower, Worst case is O(log-d(n))
boolean	contains(int i)	Does the priority queue contains the index i ?
void	decreaseKey(int i, Key key)	Decreases the key associated with index i to the given key Worst case is O(log-d(n))
void	delete(int i)	Deletes the key associated to the given index Worst case is O(d*log-d(n))
int	delMin()	Deletes the minimum key Worst case is O(d*log-d(n))
void	increaseKey(int i, Key key)	Increases the key associated with index i to the given key Worst case is O(d*log-d(n))
void	insert(int i, Key key)	Associates a key with an index Worst case is O(log-d(n))
boolean	isEmpty()	Whether the priority queue is empty Worst case is O(1)
java.util.Iterator<java.lang.Integer>	iterator()	Gets 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(d*log-d(n)) hasNext() : Worst case is O(1)
Key	keyOf(int i)	Gets the key associated with index i Worst case is O(1)
int	minIndex()	Gets the index associated with the minimum key 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)

从类继承的方法 java.lang.Object

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

从接口继承的方法 java.lang.Iterable

forEach, spliterator

构造器详细资料

IndexMultiwayMinPQ

public IndexMultiwayMinPQ(int N,
                          int D)

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

参数:

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

D - dimension of the heap

抛出:

java.lang.IllegalArgumentException - if N < 0

java.lang.IllegalArgumentException - if D < 2

IndexMultiwayMinPQ

public IndexMultiwayMinPQ(int N,
                          java.util.Comparator<Key> C,
                          int D)

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

参数:

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

D - dimension of the heap

C - a Comparator over the keys

抛出:

java.lang.IllegalArgumentException - if N < 0

java.lang.IllegalArgumentException - if D < 2

方法详细资料

isEmpty

public boolean isEmpty()

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

返回:

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)

参数:

i - an index

返回:

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

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

size

public int size()

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

返回:

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

参数:

i - an index

key - a Key associated with i

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

java.lang.IllegalArgumentException - if the index is already in the queue

minIndex

public int minIndex()

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

返回:

the index associated with the minimum key

抛出:

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

minKey

public Key minKey()

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

返回:

the minimum key currently in the priority queue

抛出:

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

delMin

public int delMin()

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

返回:

the index associated with the minimum key

抛出:

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

keyOf

public Key keyOf(int i)

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

参数:

i - an index

返回:

the key associated with index i

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

java.lang.IllegalArgumentException - 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(d*log-d(n)) If the given key is lower, Worst case is O(log-d(n))

参数:

i - an index

key - the key to associate with i

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

java.lang.IllegalArgumentException - 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(log-d(n))

参数:

i - an index

key - the key to associate with i

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

java.util.NoSuchElementException - if the index has no key associated with

java.lang.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(d*log-d(n))

参数:

i - an index

key - the key to associate with i

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

java.util.NoSuchElementException - if the index has no key associated with

java.lang.IllegalArgumentException - if the given key is lower than the current key

delete

public void delete(int i)

Deletes the key associated to the given index Worst case is O(d*log-d(n))

参数:

i - an index

抛出:

java.lang.IllegalArgumentException - if the specified index is invalid

java.util.NoSuchElementException - if the given index has no key associated with

iterator

public java.util.Iterator<java.lang.Integer> iterator()

Gets 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(d*log-d(n)) hasNext() : Worst case is O(1)

指定者:

iterator 在接口中 java.lang.Iterable<Key>

返回:

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