Package edu.princeton.cs.algs4

Class MinPQ<Key>

  • Type Parameters:
    Key - the generic type of key on this priority queue
    All Implemented Interfaces:
    Iterable<Key>
    public class MinPQ<Key>
extends Object
implements Iterable<Key>
    The MinPQ class represents a priority queue of generic keys. It supports the usual insert and delete-the-minimum operations, along with methods for peeking at the minimum key, testing if the priority queue is empty, and iterating through the keys.

    This implementation uses a binary heap. The insert and delete-the-minimum operations take Θ(log n) amortized time, where n is the number of elements in the priority queue. This is an amortized bound (and not a worst-case bound) because of array resizing operations. The min, size, and is-empty operations take Θ(1) time in the worst case. 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.

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Summary

      Constructors 
      Constructor Description
      MinPQ()
      Initializes an empty priority queue.
      MinPQ​(int initCapacity)
      Initializes an empty priority queue with the given initial capacity.
      MinPQ​(int initCapacity, Comparator<Key> comparator)
      Initializes an empty priority queue with the given initial capacity, using the given comparator.
      MinPQ​(Comparator<Key> comparator)
      Initializes an empty priority queue using the given comparator.
      MinPQ​(Key[] keys)
      Initializes a priority queue from the array of keys.

    • Constructor Detail

      • MinPQ

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

      • MinPQ

        public MinPQ()
        Initializes an empty priority queue.

      • MinPQ

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

      • MinPQ

        public MinPQ​(Comparator<Key> comparator)
        Initializes an empty priority queue using the given comparator.
        Parameters:
        comparator - the order in which to compare the keys

      • MinPQ

        public MinPQ​(Key[] keys)
        Initializes a priority queue from the array of keys.

        Takes time proportional to the number of keys, using sink-based heap construction.

        Parameters:
        keys - the array of keys

    • Method Detail

      • isEmpty

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

      • size

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

      • min

        public Key min()
        Returns a smallest key on this priority queue.
        Returns:
        a smallest key on this priority queue
        Throws:
        NoSuchElementException - if this priority queue is empty

      • insert

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

      • delMin

        public Key delMin()
        Removes and returns a smallest key on this priority queue.
        Returns:
        a smallest key on this priority queue
        Throws:
        NoSuchElementException - if this priority queue is empty

      • iterator

        public Iterator<Key> iterator()
        Returns an iterator that iterates over the keys on this priority queue in ascending order.

        The iterator doesn't implement remove() since it's optional.

        Specified by:
        iterator in interface Iterable<Key>
        Returns:
        an iterator that iterates over the keys in ascending order

      • main

        public static void main​(String[] args)
        Unit tests the MinPQ data type.
        Parameters:
        args - the command-line arguments