Package dsa

Class IndexMinPQ<Key extends Comparable<Key>>

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

      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 indexMinPQ, and false otherwise.
      void delete​(int i)
      Removes the key associated with index i in this indexMinPQ.
      int delMin()
      Removes the smallest key from this indexMinPQ and returns its associated index.
      void insert​(int i, Key key)
      Associates key with index i in this indexMinPQ.
      boolean isEmpty()
      Returns true if this indexMinPQ empty, and false otherwise.
      Iterator<Integer> iterator()
      Returns an iterator to iterate over the indices in this indexMinPQ in ascending order of the associated keys.
      Key keyOf​(int i)
      Returns the key associated with index i in this indexMinPQ.
      static void main​(String[] args)
      Unit tests the data type.
      int minIndex()
      Returns the index associated with the smallest key in this indexMinPQ.
      Key minKey()
      Returns the smallest key in this indexMinPQ.
      int size()
      Returns the number of keys in this indexMinPQ.
      String toString()
      Returns a string representation of this indexMinPQ.

    • Constructor Detail

      • IndexMinPQ

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

    • Method Detail

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

      • insert

        public void insert​(int i,
                   Key key)
        Associates key with index i in this indexMinPQ.
        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 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 key in this indexMinPQ.
        Returns:
        the index associated with the smallest key in this indexMinPQ.

      • minKey

        public Key minKey()
        Returns the smallest key in this indexMinPQ.
        Returns:
        the smallest key in this indexMinPQ.

      • keyOf

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

      • delMin

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

      • delete

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

      • iterator

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

      • toString

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

      • main

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