Package dsa

Class IndexMaxPQ<T extends Comparable<T>>

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

  • Constructor Summary

    Constructors
    Constructor
    Description
    IndexMaxPQ(int maxN)
    Constructs an empty indexMaxPQ 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 indexMaxPQ, and false otherwise.
    void
    delete(int i)
    Removes the item associated with index i in this indexMaxPQ.
    int
    deleteMax()
    Removes the largest item from this indexMaxPQ and returns its associated index.
    void
    insert(int i, T item)
    Associates item with index i in this indexMaxPQ.
    boolean
    isEmpty()
    Returns true if this indexMaxPQ empty, and false otherwise.
    T
    itemAt(int i)
    Returns the item associated with index i in this indexMaxPQ.
    Iterator<Integer>
    iterator()
    Returns an iterator to iterate over the indices in this indexMaxPQ in descending order of the associated items.
    static void
    main(String[] args)
    Unit tests the data type.
    int
    maxIndex()
    Returns the index associated with the largest item in this indexMaxPQ.
    T
    maxItem()
    Returns the largest item in this indexMaxPQ.
    int
    size()
    Returns the number of items in this indexMaxPQ.
    String
    toString()
    Returns a string representation of this indexMaxPQ.

    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

    • IndexMaxPQ

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

  • Method Details

    • isEmpty

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

    • size

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

    • insert

      public void insert(int i, T item)
      Associates item with index i in this indexMaxPQ.
      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 indexMaxPQ, and false otherwise.
      Parameters:
      i - an index.
      Returns:
      true if i is an index in this indexMaxPQ, and false otherwise.

    • maxIndex

      public int maxIndex()
      Returns the index associated with the largest item in this indexMaxPQ.
      Returns:
      the index associated with the largest item in this indexMaxPQ.

    • maxItem

      public T maxItem()
      Returns the largest item in this indexMaxPQ.
      Returns:
      the largest item in this indexMaxPQ.

    • itemAt

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

    • deleteMax

      public int deleteMax()
      Removes the largest item from this indexMaxPQ and returns its associated index.
      Returns:
      the index associated with the largest item in this indexMaxPQ.

    • delete

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

    • toString

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

    • iterator

      public Iterator<Integer> iterator()
      Returns an iterator to iterate over the indices in this indexMaxPQ in descending 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 indexMaxPQ in descending order of the associated items.

    • main

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