程序包 edu.princeton.cs.algs4

类 IndexFibonacciMinPQ<Key>

  • 所有已实现的接口:
    java.lang.Iterable<java.lang.Integer>
    public class IndexFibonacciMinPQ<Key>
extends java.lang.Object
implements java.lang.Iterable<java.lang.Integer>

    • 构造器概要

      构造器 
      构造器 说明
      IndexFibonacciMinPQ​(int N)
      Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)
      IndexFibonacciMinPQ​(java.util.Comparator<Key> C, int N)
      Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)

    • 方法概要

      修饰符和类型 方法 说明
      void changeKey​(int i, Key key)
      Changes the key associated with index i to the given key If the given key is greater, Worst case is O(log(n)) If the given key is lower, Worst case is O(1) (amortized)
      boolean contains​(int i)
      Does the priority queue contains the index i ?
      void decreaseKey​(int i, Key key)
      Decreases the key associated with index i to the given key Worst case is O(1) (amortized).
      void delete​(int i)
      Deletes the key associated the given index Worst case is O(log(n)) (amortized)
      int delMin()
      Delete the minimum key Worst case is O(log(n)) (amortized)
      void increaseKey​(int i, Key key)
      Increases the key associated with index i to the given key Worst case is O(log(n))
      void insert​(int i, Key key)
      Associates a key with an index Worst case is O(1)
      boolean isEmpty()
      Whether the priority queue is empty Worst case is O(1)
      java.util.Iterator<java.lang.Integer> iterator()
      Get an Iterator over the indexes in the priority queue in ascending order The Iterator does not implement the remove() method iterator() : Worst case is O(n) next() : Worst case is O(log(n)) (amortized) hasNext() : Worst case is O(1)
      Key keyOf​(int i)
      Get the key associated with index i Worst case is O(1)
      int minIndex()
      Get the index associated with the minimum key Worst case is O(1)
      Key minKey()
      Get the minimum key currently in the queue Worst case is O(1)
      int size()
      Number of elements currently on the priority queue Worst case is O(1)

      • 从类继承的方法 java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

      • 从接口继承的方法 java.lang.Iterable

        forEach, spliterator

    • 构造器详细资料

      • IndexFibonacciMinPQ

        public IndexFibonacciMinPQ​(int N)
        Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)
        参数:
        N - number of keys in the priority queue, index from 0 to N-1
        抛出:
        java.lang.IllegalArgumentException - if N < 0

      • IndexFibonacciMinPQ

        public IndexFibonacciMinPQ​(java.util.Comparator<Key> C,
                           int N)
        Initializes an empty indexed priority queue with indices between 0 and N-1 Worst case is O(n)
        参数:
        N - number of keys in the priority queue, index from 0 to N-1
        C - a Comparator over the keys
        抛出:
        java.lang.IllegalArgumentException - if N < 0

    • 方法详细资料

      • isEmpty

        public boolean isEmpty()
        Whether the priority queue is empty Worst case is O(1)
        返回:
        true if the priority queue is empty, false if not

      • contains

        public boolean contains​(int i)
        Does the priority queue contains the index i ? Worst case is O(1)
        参数:
        i - an index
        返回:
        true if i is on the priority queue, false if not
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid

      • size

        public int size()
        Number of elements currently on the priority queue Worst case is O(1)
        返回:
        the number of elements on the priority queue

      • insert

        public void insert​(int i,
                   Key key)
        Associates a key with an index Worst case is O(1)
        参数:
        i - an index
        key - a Key associated with i
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid
        java.lang.IllegalArgumentException - if the index is already in the queue

      • minIndex

        public int minIndex()
        Get the index associated with the minimum key Worst case is O(1)
        返回:
        the index associated with the minimum key
        抛出:
        java.util.NoSuchElementException - if the priority queue is empty

      • minKey

        public Key minKey()
        Get the minimum key currently in the queue Worst case is O(1)
        返回:
        the minimum key currently in the priority queue
        抛出:
        java.util.NoSuchElementException - if the priority queue is empty

      • delMin

        public int delMin()
        Delete the minimum key Worst case is O(log(n)) (amortized)
        返回:
        the index associated with the minimum key
        抛出:
        java.util.NoSuchElementException - if the priority queue is empty

      • keyOf

        public Key keyOf​(int i)
        Get the key associated with index i Worst case is O(1)
        参数:
        i - an index
        返回:
        the key associated with index i
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid
        java.util.NoSuchElementException - if the index is not in the queue

      • changeKey

        public void changeKey​(int i,
                      Key key)
        Changes the key associated with index i to the given key If the given key is greater, Worst case is O(log(n)) If the given key is lower, Worst case is O(1) (amortized)
        参数:
        i - an index
        key - the key to associate with i
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid
        java.util.NoSuchElementException - if the index has no key associated with

      • decreaseKey

        public void decreaseKey​(int i,
                        Key key)
        Decreases the key associated with index i to the given key Worst case is O(1) (amortized).
        参数:
        i - an index
        key - the key to associate with i
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid
        java.util.NoSuchElementException - if the index has no key associated with
        java.lang.IllegalArgumentException - if the given key is greater than the current key

      • increaseKey

        public void increaseKey​(int i,
                        Key key)
        Increases the key associated with index i to the given key Worst case is O(log(n))
        参数:
        i - an index
        key - the key to associate with i
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid
        java.util.NoSuchElementException - if the index has no key associated with
        java.lang.IllegalArgumentException - if the given key is lower than the current key

      • delete

        public void delete​(int i)
        Deletes the key associated the given index Worst case is O(log(n)) (amortized)
        参数:
        i - an index
        抛出:
        java.lang.IllegalArgumentException - if the specified index is invalid
        java.util.NoSuchElementException - if the given index has no key associated with

      • iterator

        public java.util.Iterator<java.lang.Integer> iterator()
        Get an Iterator over the indexes in the priority queue in ascending order The Iterator does not implement the remove() method iterator() : Worst case is O(n) next() : Worst case is O(log(n)) (amortized) hasNext() : Worst case is O(1)
        指定者:
        iterator 在接口中 java.lang.Iterable<Key>
        返回:
        an Iterator over the indexes in the priority queue in ascending order