Package com.zybooks.dsaj.pq

Class SortedPriorityQueue<K,V>

java.lang.Object

com.zybooks.dsaj.pq.AbstractPriorityQueue<K,V>

com.zybooks.dsaj.pq.SortedPriorityQueue<K,V>

Type Parameters:

K - The key type (keys must be unique and comparable)

V - The value type stored with each entry

All Implemented Interfaces:

PriorityQueue<K,V>

public class SortedPriorityQueue<K,V>
extends AbstractPriorityQueue<K,V>

An implementation of a priority queue with a sorted list.

Nested Class Summary

Nested classes/interfaces inherited from class com.zybooks.dsaj.pq.AbstractPriorityQueue

AbstractPriorityQueue.PQEntry<K,V>

Constructor Summary

Constructors

Constructor	Description
SortedPriorityQueue()	Creates an empty priority queue based on the natural ordering of its keys.
SortedPriorityQueue(Comparator<K> comp)	Creates an empty priority queue using the given comparator to order keys.

Method Summary

Modifier and Type	Method	Description
Entry<K,V>	insert(K key, V value)	Inserts a key-value pair and returns the entry created.
Entry<K,V>	min()	Returns (but does not remove) an entry with minimal key.
Entry<K,V>	removeMin()	Removes and returns an entry with minimal key.
int	size()	Returns the number of items in the priority queue.

Methods inherited from class com.zybooks.dsaj.pq.AbstractPriorityQueue

compare, createEntry, isEmpty

Methods inherited from class java.lang.Object

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

Constructor Details

SortedPriorityQueue

public SortedPriorityQueue()

Creates an empty priority queue based on the natural ordering of its keys.

SortedPriorityQueue

public SortedPriorityQueue(Comparator<K> comp)

Creates an empty priority queue using the given comparator to order keys.

Parameters:

comp - comparator defining the order of keys in the priority queue

Method Details

insert

public Entry<K,V> insert(K key,
 V value)

Inserts a key-value pair and returns the entry created.

Parameters:

key - the key of the new entry

value - the associated value of the new entry

Returns:

the entry storing the new key-value pair

min

public Entry<K,V> min()

Returns (but does not remove) an entry with minimal key.

Returns:

entry having a minimal key (or null if empty)

removeMin

public Entry<K,V> removeMin()

Removes and returns an entry with minimal key.

Returns:

the removed entry (or null if empty)

size

public int size()

Returns the number of items in the priority queue.

Returns:

number of items