Package dsa

Class IndexMaxPQ<Key extends Comparable<Key>>

  • All Implemented Interfaces:
    Iterable<Integer>
    public class IndexMaxPQ<Key extends Comparable<Key>>
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

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      void change​(int i, Key key)
      Changes the key associated with index i to key.
      boolean contains​(int i)
      Returns true if i is an index in this indexMaxPQ, and false otherwise.
      void delete​(int i)
      Removes the key associated with index i in this indexMaxPQ.
      int delMax()
      Removes the largest key from this indexMaxPQ and returns its associated index.
      void insert​(int i, Key key)
      Associates key with index i in this indexMaxPQ.
      boolean isEmpty()
      Returns true if this indexMaxPQ empty, and false otherwise.
      Iterator<Integer> iterator()
      Returns an iterator to iterate over the indices in this indexMaxPQ in descending order of the associated keys.
      Key keyOf​(int i)
      Returns the key associated with index i in this indexMaxPQ.
      static void main​(String[] args)
      Unit tests the data type.
      int maxIndex()
      Returns the index associated with the largest key in this indexMaxPQ.
      Key maxKey()
      Returns the largest key in this indexMaxPQ.
      int size()
      Returns the number of keys in this indexMaxPQ.
      String toString()
      Returns a string representation of this indexMaxPQ.

    • Constructor Detail

      • IndexMaxPQ

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

    • Method Detail

      • 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 keys in this indexMaxPQ.
        Returns:
        the number of keys in this indexMaxPQ.

      • insert

        public void insert​(int i,
                   Key key)
        Associates key with index i in this indexMaxPQ.
        Parameters:
        i - the index.
        key - the key.

      • change

        public void change​(int i,
                   Key key)
        Changes the key associated with index i to key.
        Parameters:
        i - the index.
        key - the key.

      • 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 key in this indexMaxPQ.
        Returns:
        the index associated with the largest key in this indexMaxPQ.

      • maxKey

        public Key maxKey()
        Returns the largest key in this indexMaxPQ.
        Returns:
        the largest key in this indexMaxPQ.

      • keyOf

        public Key keyOf​(int i)
        Returns the key associated with index i in this indexMaxPQ.
        Parameters:
        i - the index.
        Returns:
        the key associated with index i in this indexMaxPQ.

      • delMax

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

      • delete

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

      • iterator

        public Iterator<Integer> iterator()
        Returns an iterator to iterate over the indices in this indexMaxPQ in descending order of the associated keys.
        Specified by:
        iterator in interface Iterable<Key extends Comparable<Key>>
        Returns:
        an iterator to iterate over the indices in this indexMaxPQ in descending order of the associated keys.

      • toString

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

      • main

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