Package graph

Class MinPQueue<KeyType>

java.lang.Object

graph.MinPQueue<KeyType>

public class MinPQueue<KeyType>
extends Object

A min priority queue of distinct elements of type `KeyType` associated with (extrinsic) double priorities, implemented using a binary heap paired with a hash table.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static final record	MinPQueue.Entry<KeyType>	Pairs an element `key` with its associated priority `priority`.

Field Summary

Fields

Modifier and Type	Field	Description
private final ArrayList<MinPQueue.Entry<KeyType>>	heap	ArrayList representing a binary min-heap of element-priority pairs.
private final Map<KeyType,Integer>	index	Associates each element in the queue with its index in `heap`.

Constructor Summary

Constructors

Constructor	Description
MinPQueue()	Create an empty queue.

Method Summary

Modifier and Type	Method	Description
private void	add(KeyType key, double priority)	Add element `key` to this queue, associated with priority `priority`.
void	addOrUpdate(KeyType key, double priority)	If `key` is already contained in this queue, change its associated priority to `priority`.
boolean	isEmpty()	Return whether this queue contains no elements.
double	minPriority()	Return the minimum priority associated with an element in this queue.
KeyType	peek()	Return an element associated with the smallest priority in this queue.
KeyType	remove()	Remove and return the element associated with the smallest priority in this queue.
int	size()	Return the number of elements contained in this queue.
private void	swap(int i, int j)	Swap the Entries at indices `i` and `j` in `heap`, updating `index` accordingly.
private void	update(KeyType key, double priority)	Change the priority associated with element `key` to `priority`.

Methods inherited from class java.lang.Object

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

Field Details

heap

private final ArrayList<MinPQueue.Entry<KeyType>> heap

ArrayList representing a binary min-heap of element-priority pairs. Satisfies `heap.get(i).priority() >= heap.get((i-1)/2).priority()` for all `i` in `[1..heap.size())`.

index

private final Map<KeyType,Integer> index

Associates each element in the queue with its index in `heap`. Satisfies `heap.get(index.get(e)).key().equals(e)` if `e` is an element in the queue. Only maps elements that are in the queue (`index.size() == heap.size()`).

Constructor Details

MinPQueue

public MinPQueue()

Create an empty queue.

Method Details

isEmpty

public boolean isEmpty()

Return whether this queue contains no elements.

size

public int size()

Return the number of elements contained in this queue.

peek

public KeyType peek()

Return an element associated with the smallest priority in this queue. This is the same element that would be removed by a call to `remove()` (assuming no mutations in between). Throws NoSuchElementException if this queue is empty.

minPriority

public double minPriority()

Return the minimum priority associated with an element in this queue. Throws NoSuchElementException if this queue is empty.

swap

private void swap(int i,
 int j)

Swap the Entries at indices `i` and `j` in `heap`, updating `index` accordingly. Requires 0 <= i,j < heap.size().

add

private void add(KeyType key,
 double priority)

Add element `key` to this queue, associated with priority `priority`. Requires `key` is not contained in this queue.

update

private void update(KeyType key,
 double priority)

Change the priority associated with element `key` to `priority`. Requires that `key` is contained in this queue.

addOrUpdate

public void addOrUpdate(KeyType key,
 double priority)

If `key` is already contained in this queue, change its associated priority to `priority`. Otherwise, add it to this queue with that priority.

remove

public KeyType remove()

Remove and return the element associated with the smallest priority in this queue. If multiple elements are tied for the smallest priority, an arbitrary one will be removed. Throws NoSuchElementException if this queue is empty.