程序包 edu.princeton.cs.algs4

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

  • 类型参数:
    Key - the generic type of key on this priority queue
    所有已实现的接口:
    java.lang.Iterable<java.lang.Integer>
    public class IndexMaxPQ<Key extends java.lang.Comparable<Key>>
extends java.lang.Object
implements java.lang.Iterable<java.lang.Integer>
    The IndexMaxPQ class represents an indexed priority queue of generic keys. It supports the usual insert and delete-the-maximum operations, along with delete and change-the-key methods. In order to let the client refer to items 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 a maximum 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-maximum, delete, change-key, decrease-key, and increase-key operations take logarithmic time. The is-empty, size, max-index, max-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.

    • 构造器概要

      构造器 
      构造器 说明
      IndexMaxPQ​(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 on the priority queue associated with index i.
      int delMax()
      Removes a maximum 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)
      Associate 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 descending order.
      Key keyOf​(int i)
      Returns the key associated with index i.
      static void main​(java.lang.String[] args)
      Unit tests the IndexMaxPQ data type.
      int maxIndex()
      Returns an index associated with a maximum key.
      Key maxKey()
      Returns a maximum 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

    • 构造器详细资料

      • IndexMaxPQ

        public IndexMaxPQ​(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 to 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)
        Associate 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

      • maxIndex

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

      • maxKey

        public Key maxKey()
        Returns a maximum key.
        返回:
        a maximum key
        抛出:
        java.util.NoSuchElementException - if this priority queue is empty

      • delMax

        public int delMax()
        Removes a maximum key and returns its associated index.
        返回:
        an index associated with a maximum 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

      • 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

      • 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

      • 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

      • delete

        public void delete​(int i)
        Remove the key on the priority queue 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 descending 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 descending order

      • main

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