Package dsa

Class MaxPQ<T>

java.lang.Object
dsa.MaxPQ<T>
Type Parameters:
T - the type of items in the pq.
All Implemented Interfaces:
Iterable<T>
public class MaxPQ<T> extends Object implements Iterable<T>
A data type to represent a maximum priority queue (maxPQ) data structure, implemented using a binary max-heap.

  • Constructor Summary

    Constructors
    Constructor
    Description
    MaxPQ()
    Constructs an empty maxPQ.
    MaxPQ(int capacity)
    Constructs an empty maxPQ with the given capacity.
    MaxPQ(int capacity, Comparator<T> c)
    Constructs an empty maxPQ with the given capacity and comparator.
    MaxPQ(Comparator<T> c)
    Construct an empty maxPQ with the given comparator.

  • Method Summary

    Modifier and Type
    Method
    Description
    T
    deleteMax()
    Removes and returns the largest item in this maxPQ.
    void
    insert(T item)
    Adds item to this maxPQ.
    boolean
    isEmpty()
    Returns true if this maxPQ empty, and false otherwise.
    Iterator<T>
    iterator()
    Returns an iterator to iterate over the items in this maxPQ in descending order.
    static void
    main(String[] args)
    Unit tests the data type.
    T
    max()
    Returns the largest item in this maxPQ.
    int
    size()
    Returns the number of items in this maxPQ.
    String
    toString()
    Returns a string representation of this maxPQ.

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Constructor Details

    • MaxPQ

      public MaxPQ()
      Constructs an empty maxPQ.

    • MaxPQ

      public MaxPQ(Comparator<T> c)
      Construct an empty maxPQ with the given comparator.
      Parameters:
      c - the comparator.

    • MaxPQ

      public MaxPQ(int capacity)
      Constructs an empty maxPQ with the given capacity.
      Parameters:
      capacity - the capacity.

    • MaxPQ

      public MaxPQ(int capacity, Comparator<T> c)
      Constructs an empty maxPQ with the given capacity and comparator.
      Parameters:
      capacity - the capacity.
      c - the comparator.

  • Method Details

    • isEmpty

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

    • size

      public int size()
      Returns the number of items in this maxPQ.
      Returns:
      the number of items in this maxPQ.

    • insert

      public void insert(T item)
      Adds item to this maxPQ.
      Parameters:
      item - the item.

    • max

      public T max()
      Returns the largest item in this maxPQ.
      Returns:
      the largest item in this maxPQ.

    • deleteMax

      public T deleteMax()
      Removes and returns the largest item in this maxPQ.
      Returns:
      the largest item in this maxPQ.

    • toString

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

    • iterator

      public Iterator<T> iterator()
      Returns an iterator to iterate over the items in this maxPQ in descending order.
      Specified by:
      iterator in interface Iterable<T>
      Returns:
      an iterator to iterate over the items in this maxPQ in descending order.

    • main

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