Package dsa

Class MinPQ<Key>

  • All Implemented Interfaces:
    Iterable<Key>
    public class MinPQ<Key>
extends Object
implements Iterable<Key>
    A data type to represent a minimum priority queue (minPQ) data structure, implemented using a binary min-heap.

    • Constructor Detail

      • MinPQ

        public MinPQ()
        Constructs an empty minPQ.

      • MinPQ

        public MinPQ​(Comparator<Key> c)
        Construct an empty minPQ with the given comparator.
        Parameters:
        c - the comparator.

      • MinPQ

        public MinPQ​(int capacity)
        Constructs an empty minPQ with the given capacity.
        Parameters:
        capacity - the capacity.

      • MinPQ

        public MinPQ​(int capacity,
             Comparator<Key> c)
        Constructs an empty minPQ with the given capacity and comparator.
        Parameters:
        capacity - the capacity.
        c - the comparator.

    • Method Detail

      • isEmpty

        public boolean isEmpty()
        Returns true if this minPQ empty, and false otherwise.
        Returns:
        true if this minPQ empty, and false otherwise.

      • size

        public int size()
        Returns the number of keys in this minPQ.
        Returns:
        the number of keys in this minPQ.

      • insert

        public void insert​(Key key)
        Adds key to this minPQ.
        Parameters:
        key - the key.

      • min

        public Key min()
        Returns the smallest key in this minPQ.
        Returns:
        the smallest key in this minPQ.

      • delMin

        public Key delMin()
        Removes and returns the smallest key in this minPQ.
        Returns:
        the smallest key in this minPQ.

      • iterator

        public Iterator<Key> iterator()
        Returns an iterator to iterate over the keys in this minPQ in ascending order.
        Specified by:
        iterator in interface Iterable<Key>
        Returns:
        an iterator to iterate over the keys in this minPQ in ascending order.

      • toString

        public String toString()
        Returns a string representation of this minPQ.
        Overrides:
        toString in class Object
        Returns:
        a string representation of this minPQ.

      • main

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