Package dsa

Class IndexMinPQ<T extends Comparable<T>>

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    IndexMinPQ(int maxN)
    Constructs an empty indexMinPQ with indices from the interval [0, maxN).

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    change(int i, T item)
    Changes the item associated with index i to item.
    boolean
    contains(int i)
    Returns true if i is an index in this indexMinPQ, and false otherwise.
    void
    delete(int i)
    Removes the item associated with index i in this indexMinPQ.
    int
    deleteMin()
    Removes the smallest item from this indexMinPQ and returns its associated index.
    void
    insert(int i, T item)
    Associates item with index i in this indexMinPQ.
    boolean
    isEmpty()
    Returns true if this indexMinPQ empty, and false otherwise.
    T
    itemAt(int i)
    Returns the item associated with index i in this indexMinPQ.
    Iterator<Integer>
    iterator()
    Returns an iterator to iterate over the indices in this indexMinPQ in ascending order of the associated items.
    static void
    main(String[] args)
    Unit tests the data type.
    int
    minIndex()
    Returns the index associated with the smallest item in this indexMinPQ.
    T
    minItem()
    Returns the smallest item in this indexMinPQ.
    int
    size()
    Returns the number of items in this indexMinPQ.
    String
    toString()
    Returns a string representation of this indexMinPQ.

    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

    • IndexMinPQ

      public IndexMinPQ(int maxN)
      Constructs an empty indexMinPQ with indices from the interval [0, maxN).
      Parameters:
      maxN - the items in this indexMinPQ have indices from the interval [0, maxN).

  • Method Details

    • isEmpty

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

    • size

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

    • insert

      public void insert(int i, T item)
      Associates item with index i in this indexMinPQ.
      Parameters:
      i - the index.
      item - the item.

    • change

      public void change(int i, T item)
      Changes the item associated with index i to item.
      Parameters:
      i - the index.
      item - the item.

    • contains

      public boolean contains(int i)
      Returns true if i is an index in this indexMinPQ, and false otherwise.
      Parameters:
      i - an index.
      Returns:
      true if i is an index in this indexMinPQ, and false otherwise.

    • minIndex

      public int minIndex()
      Returns the index associated with the smallest item in this indexMinPQ.
      Returns:
      the index associated with the smallest item in this indexMinPQ.

    • minItem

      public T minItem()
      Returns the smallest item in this indexMinPQ.
      Returns:
      the smallest item in this indexMinPQ.

    • itemAt

      public T itemAt(int i)
      Returns the item associated with index i in this indexMinPQ.
      Parameters:
      i - the index.
      Returns:
      the item associated with index i in this indexMinPQ.

    • deleteMin

      public int deleteMin()
      Removes the smallest item from this indexMinPQ and returns its associated index.
      Returns:
      the index associated with the smallest item in this indexMinPQ.

    • delete

      public void delete(int i)
      Removes the item associated with index i in this indexMinPQ.
      Parameters:
      i - the index.

    • toString

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

    • iterator

      public Iterator<Integer> iterator()
      Returns an iterator to iterate over the indices in this indexMinPQ in ascending order of the associated items.
      Specified by:
      iterator in interface Iterable<T extends Comparable<T>>
      Returns:
      an iterator to iterate over the indices in this indexMinPQ in ascending order of the associated items.

    • main

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