类 IndexMinPQ<Key extends java.lang.Comparable<Key>>

  • 类型参数:
    Key - the generic type of key on this priority queue
    所有已实现的接口:
    java.lang.Iterable<java.lang.Integer>

    public class IndexMinPQ<Key extends java.lang.Comparable<Key>>
    extends java.lang.Object
    implements java.lang.Iterable<java.lang.Integer>
    The IndexMinPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with delete and change-the-key methods. In order to let the client refer to keys on the priority queue, an integer between 0 and maxN - 1 is associated with each key—the client uses this integer to specify which key to delete or change. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys.

    This implementation uses a binary heap along with an array to associate keys with integers in the given range. The insert, delete-the-minimum, delete, change-key, decrease-key, and increase-key operations take logarithmic time. The is-empty, size, min-index, min-key, contains, and key-of operations take constant time. Construction takes time proportional to the specified capacity.

    For additional documentation, see Section 2.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    • 构造器概要

      构造器 
      构造器 说明
      IndexMinPQ​(int maxN)
      Initializes an empty indexed priority queue with indices between 0 and maxN - 1.
    • 方法概要

      修饰符和类型 方法 说明
      void change​(int i, Key key)
      已过时。
      Replaced by changeKey(int, Key).
      void changeKey​(int i, Key key)
      Change the key associated with index i to the specified value.
      boolean contains​(int i)
      Is i an index on this priority queue?
      void decreaseKey​(int i, Key key)
      Decrease the key associated with index i to the specified value.
      void delete​(int i)
      Remove the key associated with index i.
      int delMin()
      Removes a minimum key and returns its associated index.
      void increaseKey​(int i, Key key)
      Increase the key associated with index i to the specified value.
      void insert​(int i, Key key)
      Associates key with index i.
      boolean isEmpty()
      Returns true if this priority queue is empty.
      java.util.Iterator<java.lang.Integer> iterator()
      Returns an iterator that iterates over the keys on the priority queue in ascending order.
      Key keyOf​(int i)
      Returns the key associated with index i.
      static void main​(java.lang.String[] args)
      Unit tests the IndexMinPQ data type.
      int minIndex()
      Returns an index associated with a minimum key.
      Key minKey()
      Returns a minimum key.
      int size()
      Returns the number of keys on this priority queue.
      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • 从接口继承的方法 java.lang.Iterable

        forEach, spliterator
    • 构造器详细资料

      • IndexMinPQ

        public IndexMinPQ​(int maxN)
        Initializes an empty indexed priority queue with indices between 0 and maxN - 1.
        参数:
        maxN - the keys on this priority queue are index from 0 maxN - 1
        抛出:
        java.lang.IllegalArgumentException - if maxN < 0
    • 方法详细资料

      • isEmpty

        public boolean isEmpty()
        Returns true if this priority queue is empty.
        返回:
        true if this priority queue is empty; false otherwise
      • contains

        public boolean contains​(int i)
        Is i an index on this priority queue?
        参数:
        i - an index
        返回:
        true if i is an index on this priority queue; false otherwise
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
      • size

        public int size()
        Returns the number of keys on this priority queue.
        返回:
        the number of keys on this priority queue
      • insert

        public void insert​(int i,
                           Key key)
        Associates key with index i.
        参数:
        i - an index
        key - the key to associate with index i
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
        java.lang.IllegalArgumentException - if there already is an item associated with index i
      • minIndex

        public int minIndex()
        Returns an index associated with a minimum key.
        返回:
        an index associated with a minimum key
        抛出:
        java.util.NoSuchElementException - if this priority queue is empty
      • minKey

        public Key minKey()
        Returns a minimum key.
        返回:
        a minimum key
        抛出:
        java.util.NoSuchElementException - if this priority queue is empty
      • delMin

        public int delMin()
        Removes a minimum key and returns its associated index.
        返回:
        an index associated with a minimum key
        抛出:
        java.util.NoSuchElementException - if this priority queue is empty
      • keyOf

        public Key keyOf​(int i)
        Returns the key associated with index i.
        参数:
        i - the index of the key to return
        返回:
        the key associated with index i
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
        java.util.NoSuchElementException - no key is associated with index i
      • changeKey

        public void changeKey​(int i,
                              Key key)
        Change the key associated with index i to the specified value.
        参数:
        i - the index of the key to change
        key - change the key associated with index i to this key
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
        java.util.NoSuchElementException - no key is associated with index i
      • change

        @Deprecated
        public void change​(int i,
                           Key key)
        已过时。
        Replaced by changeKey(int, Key).
        Change the key associated with index i to the specified value.
        参数:
        i - the index of the key to change
        key - change the key associated with index i to this key
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
      • decreaseKey

        public void decreaseKey​(int i,
                                Key key)
        Decrease the key associated with index i to the specified value.
        参数:
        i - the index of the key to decrease
        key - decrease the key associated with index i to this key
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
        java.lang.IllegalArgumentException - if key >= keyOf(i)
        java.util.NoSuchElementException - no key is associated with index i
      • increaseKey

        public void increaseKey​(int i,
                                Key key)
        Increase the key associated with index i to the specified value.
        参数:
        i - the index of the key to increase
        key - increase the key associated with index i to this key
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
        java.lang.IllegalArgumentException - if key <= keyOf(i)
        java.util.NoSuchElementException - no key is associated with index i
      • delete

        public void delete​(int i)
        Remove the key associated with index i.
        参数:
        i - the index of the key to remove
        抛出:
        java.lang.IllegalArgumentException - unless 0 <= i < maxN
        java.util.NoSuchElementException - no key is associated with index i
      • iterator

        public java.util.Iterator<java.lang.Integer> iterator()
        Returns an iterator that iterates over the keys on the priority queue in ascending order. The iterator doesn't implement remove() since it's optional.
        指定者:
        iterator 在接口中 java.lang.Iterable<Key extends java.lang.Comparable<Key>>
        返回:
        an iterator that iterates over the keys in ascending order
      • main

        public static void main​(java.lang.String[] args)
        Unit tests the IndexMinPQ data type.
        参数:
        args - the command-line arguments