Package edu.princeton.cs.algs4

Class MultiwayMinPQ<Key>

  • All Implemented Interfaces:
    Iterable<Key>
    public class MultiwayMinPQ<Key>
extends Object
implements Iterable<Key>
    The MultiwayMinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum operations. 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 multiway heap. For simplified notations, logarithm in base d will be referred as log-d The delete-the-minimum operation takes time proportional to d*log-d(n) The insert takes time proportional to log-d(n) The is-empty, min-key and size operations take constant time. Constructor takes time proportional to the specified capacity.
    Author:
    Tristan Claverie

    • Constructor Summary

      Constructors 
      Constructor Description
      MultiwayMinPQ​(int d)
      Initializes an empty priority queue Worst case is O(d)
      MultiwayMinPQ​(Comparator<Key> comparator, int d)
      Initializes an empty priority queue Worst case is O(d)
      MultiwayMinPQ​(Comparator<Key> comparator, Key[] a, int d)
      Initializes a priority queue with given indexes Worst case is O(a*log-d(n))
      MultiwayMinPQ​(Key[] a, int d)
      Initializes a priority queue with given indexes Worst case is O(n*log-d(n))

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      Key delMin()
      Deletes the minimum key Worst case is O(d*log-d(n))
      void insert​(Key key)
      Puts a Key on the priority queue Worst case is O(log-d(n))
      boolean isEmpty()
      Whether the priority queue is empty Worst case is O(1)
      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(d*log-d(n)) hasNext() : Worst case is O(1)
      Key minKey()
      Gets 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)

    • Constructor Detail

      • MultiwayMinPQ

        public MultiwayMinPQ​(int d)
        Initializes an empty priority queue Worst case is O(d)
        Parameters:
        d - dimension of the heap
        Throws:
        IllegalArgumentException - if d < 2

      • MultiwayMinPQ

        public MultiwayMinPQ​(Comparator<Key> comparator,
                     int d)
        Initializes an empty priority queue Worst case is O(d)
        Parameters:
        d - dimension of the heap
        comparator - a Comparator over the keys
        Throws:
        IllegalArgumentException - if d < 2

      • MultiwayMinPQ

        public MultiwayMinPQ​(Key[] a,
                     int d)
        Initializes a priority queue with given indexes Worst case is O(n*log-d(n))
        Parameters:
        d - dimension of the heap
        a - an array of keys
        Throws:
        IllegalArgumentException - if d < 2

      • MultiwayMinPQ

        public MultiwayMinPQ​(Comparator<Key> comparator,
                     Key[] a,
                     int d)
        Initializes a priority queue with given indexes Worst case is O(a*log-d(n))
        Parameters:
        d - dimension of the heap
        comparator - a Comparator over the keys
        a - an array of keys
        Throws:
        IllegalArgumentException - if d < 2

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Whether the priority queue is empty Worst case is O(1)
        Returns:
        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(1)
        Returns:
        the number of elements on the priority queue

      • insert

        public void insert​(Key key)
        Puts a Key on the priority queue Worst case is O(log-d(n))
        Parameters:
        key - a Key

      • minKey

        public Key minKey()
        Gets the minimum key currently in the queue Worst case is O(1)
        Returns:
        the minimum key currently in the priority queue
        Throws:
        NoSuchElementException - if the priority queue is empty

      • delMin

        public Key delMin()
        Deletes the minimum key Worst case is O(d*log-d(n))
        Returns:
        the minimum key
        Throws:
        NoSuchElementException - if the priority queue is empty

      • iterator

        public 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(d*log-d(n)) hasNext() : Worst case is O(1)
        Specified by:
        iterator in interface Iterable<Key>
        Returns:
        an Iterator over the keys in the priority queue in ascending order