Package dsa

Class MinPQ<T>

java.lang.Object
dsa.MinPQ<T>
Type Parameters:
T - the type of items in the pq.
All Implemented Interfaces:
Iterable<T>
public class MinPQ<T> extends Object implements Iterable<T>
A data type to represent a minimum priority queue (minPQ) data structure, implemented using a binary min-heap.

  • Constructor Summary

    Constructors
    Constructor
    Description
    MinPQ()
    Constructs an empty minPQ.
    MinPQ(int capacity)
    Constructs an empty minPQ with the given capacity.
    MinPQ(int capacity, Comparator<T> c)
    Constructs an empty minPQ with the given capacity and comparator.
    MinPQ(Comparator<T> c)
    Constructs an empty minPQ with the given comparator.

  • Method Summary

    Modifier and Type
    Method
    Description
    T
    deleteMin()
    Removes and returns the smallest item in this minPQ.
    void
    insert(T item)
    Adds item to this minPQ.
    boolean
    isEmpty()
    Returns true if this minPQ empty, and false otherwise.
    Iterator<T>
    iterator()
    Returns an iterator to iterate over the items in this minPQ in ascending order.
    static void
    main(String[] args)
    Unit tests the data type.
    T
    min()
    Returns the smallest item in this minPQ.
    int
    size()
    Returns the number of items in this minPQ.
    String
    toString()
    Returns a string representation of this minPQ.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • MinPQ

      public MinPQ()
      Constructs an empty minPQ.

    • MinPQ

      public MinPQ(Comparator<T> c)
      Constructs an empty minPQ with the given comparator.
      Parameters:
      c - the comparator.

    • MinPQ

      public MinPQ(int capacity)
      Constructs an empty minPQ with the given capacity.
      Parameters:
      capacity - the capacity.

    • MinPQ

      public MinPQ(int capacity, Comparator<T> c)
      Constructs an empty minPQ with the given capacity and comparator.
      Parameters:
      capacity - the capacity.
      c - the comparator.

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Returns true if this minPQ empty, and false otherwise.
      Returns:
      true if this minPQ empty, and false otherwise.

    • size

      public int size()
      Returns the number of items in this minPQ.
      Returns:
      the number of items in this minPQ.

    • insert

      public void insert(T item)
      Adds item to this minPQ.
      Parameters:
      item - the item.

    • min

      public T min()
      Returns the smallest item in this minPQ.
      Returns:
      the smallest item in this minPQ.

    • deleteMin

      public T deleteMin()
      Removes and returns the smallest item in this minPQ.
      Returns:
      the smallest item in this minPQ.

    • toString

      public String toString()
      Returns a string representation of this minPQ.
      Overrides:
      toString in class Object
      Returns:
      a string representation of this minPQ.

    • iterator

      public Iterator<T> iterator()
      Returns an iterator to iterate over the items in this minPQ in ascending order.
      Specified by:
      iterator in interface Iterable<T>
      Returns:
      an iterator to iterate over the items in this minPQ in ascending order.

    • main

      public static void main(String[] args)
      Unit tests the data type.
      Parameters:
      args - the command-line arguments.