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.