程序包 edu.princeton.cs.algs4

类 BinomialMinPQ<Key>

  • 所有已实现的接口:
    java.lang.Iterable<Key>
    public class BinomialMinPQ<Key>
extends java.lang.Object
implements java.lang.Iterable<Key>
    The BinomialMinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with the merging of two heaps together. It also supports methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys. It is possible to build the priority queue using a Comparator. If not, the natural order relation between the keys will be used. This implementation uses a binomial heap. The insert, delete-the-minimum, union, min-key and size operations take logarithmic time. The is-empty and constructor operations take constant time.

    • 构造器概要

      构造器 
      构造器 说明
      BinomialMinPQ()
      Initializes an empty priority queue Worst case is O(1)
      BinomialMinPQ​(java.util.Comparator<Key> C)
      Initializes an empty priority queue using the given Comparator Worst case is O(1)
      BinomialMinPQ​(java.util.Comparator<Key> C, Key[] a)
      Initializes a priority queue with given keys using the given Comparator Worst case is O(n*log(n))
      BinomialMinPQ​(Key[] a)
      Initializes a priority queue with given keys Worst case is O(n*log(n))

    • 方法概要

      修饰符和类型 方法 说明
      Key delMin()
      Deletes the minimum key Worst case is O(log(n))
      void insert​(Key key)
      Puts a Key in the heap Worst case is O(log(n))
      boolean isEmpty()
      Whether the priority queue is empty Worst case is O(1)
      java.util.Iterator<Key> iterator()
      Gets an Iterator over the keys 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)) hasNext() : Worst case is O(1)
      Key minKey()
      Get the minimum key currently in the queue Worst case is O(log(n))
      int size()
      Number of elements currently on the priority queue Worst case is O(log(n))
      BinomialMinPQ<Key> union​(BinomialMinPQ<Key> heap)
      Merges two Binomial heaps together This operation is destructive Worst case is O(log(n))

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

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

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

        forEach, spliterator

    • 构造器详细资料

      • BinomialMinPQ

        public BinomialMinPQ()
        Initializes an empty priority queue Worst case is O(1)

      • BinomialMinPQ

        public BinomialMinPQ​(java.util.Comparator<Key> C)
        Initializes an empty priority queue using the given Comparator Worst case is O(1)
        参数:
        C - a comparator over the keys

      • BinomialMinPQ

        public BinomialMinPQ​(Key[] a)
        Initializes a priority queue with given keys Worst case is O(n*log(n))
        参数:
        a - an array of keys

      • BinomialMinPQ

        public BinomialMinPQ​(java.util.Comparator<Key> C,
                     Key[] a)
        Initializes a priority queue with given keys using the given Comparator Worst case is O(n*log(n))
        参数:
        C - a comparator over the keys
        a - an array of keys

    • 方法详细资料

      • 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

      • size

        public int size()
        Number of elements currently on the priority queue Worst case is O(log(n))
        返回:
        the number of elements on the priority queue
        抛出:
        java.lang.ArithmeticException - if there are more than 2^63-1 elements in the queue

      • insert

        public void insert​(Key key)
        Puts a Key in the heap Worst case is O(log(n))
        参数:
        key - a Key

      • minKey

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

      • delMin

        public Key delMin()
        Deletes the minimum key Worst case is O(log(n))
        返回:
        the minimum key
        抛出:
        java.util.NoSuchElementException - if the priority queue is empty

      • union

        public BinomialMinPQ<Key> union​(BinomialMinPQ<Key> heap)
        Merges two Binomial heaps together This operation is destructive Worst case is O(log(n))
        参数:
        heap - a Binomial Heap to be merged with the current heap
        返回:
        the union of two heaps
        抛出:
        java.lang.IllegalArgumentException - if the heap in parameter is null

      • iterator

        public java.util.Iterator<Key> iterator()
        Gets an Iterator over the keys 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)) hasNext() : Worst case is O(1)
        指定者:
        iterator 在接口中 java.lang.Iterable<Key>
        返回:
        an Iterator over the keys in the priority queue in ascending order