程序包 edu.princeton.cs.algs4

类 MaxPQ<Key>

  • 类型参数:
    Key - the generic type of key on this priority queue
    所有已实现的接口:
    java.lang.Iterable<Key>
    public class MaxPQ<Key>
extends java.lang.Object
implements java.lang.Iterable<Key>
    The MaxPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-maximum operations, along with methods for peeking at the maximum key, testing if the priority queue is empty, and iterating through the keys.

    This implementation uses a binary heap. The insert and delete-the-maximum operations take logarithmic amortized time. The max, size, and is-empty operations take constant time. Construction takes time proportional to the specified capacity or the number of items used to initialize the data structure.

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

    • 构造器概要

      构造器 
      构造器 说明
      MaxPQ()
      Initializes an empty priority queue.
      MaxPQ​(int initCapacity)
      Initializes an empty priority queue with the given initial capacity.
      MaxPQ​(int initCapacity, java.util.Comparator<Key> comparator)
      Initializes an empty priority queue with the given initial capacity, using the given comparator.
      MaxPQ​(java.util.Comparator<Key> comparator)
      Initializes an empty priority queue using the given comparator.
      MaxPQ​(Key[] keys)
      Initializes a priority queue from the array of keys.

    • 方法概要

      修饰符和类型 方法 说明
      Key delMax()
      Removes and returns a largest key on this priority queue.
      void insert​(Key x)
      Adds a new key to this priority queue.
      boolean isEmpty()
      Returns true if this priority queue is empty.
      java.util.Iterator<Key> iterator()
      Returns an iterator that iterates over the keys on this priority queue in descending order.
      static void main​(java.lang.String[] args)
      Unit tests the MaxPQ data type.
      Key max()
      Returns a largest key on this priority queue.
      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

    • 构造器详细资料

      • MaxPQ

        public MaxPQ​(int initCapacity)
        Initializes an empty priority queue with the given initial capacity.
        参数:
        initCapacity - the initial capacity of this priority queue

      • MaxPQ

        public MaxPQ()
        Initializes an empty priority queue.

      • MaxPQ

        public MaxPQ​(int initCapacity,
             java.util.Comparator<Key> comparator)
        Initializes an empty priority queue with the given initial capacity, using the given comparator.
        参数:
        initCapacity - the initial capacity of this priority queue
        comparator - the order in which to compare the keys

      • MaxPQ

        public MaxPQ​(java.util.Comparator<Key> comparator)
        Initializes an empty priority queue using the given comparator.
        参数:
        comparator - the order in which to compare the keys

      • MaxPQ

        public MaxPQ​(Key[] keys)
        Initializes a priority queue from the array of keys. Takes time proportional to the number of keys, using sink-based heap construction.
        参数:
        keys - the array of keys

    • 方法详细资料

      • isEmpty

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

      • size

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

      • max

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

      • insert

        public void insert​(Key x)
        Adds a new key to this priority queue.
        参数:
        x - the new key to add to this priority queue

      • delMax

        public Key delMax()
        Removes and returns a largest key on this priority queue.
        返回:
        a largest key on this priority queue
        抛出:
        java.util.NoSuchElementException - if this priority queue is empty

      • iterator

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

      • main

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