Package algs24

Class MaxPQ<K extends Comparable<? super K>>

java.lang.Object
algs24.MaxPQ<K>
All Implemented Interfaces:
Iterable<K>
public class MaxPQ<K extends Comparable<? super K>> extends Object implements Iterable<K>
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.

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.

This implementation uses a binary heap.

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

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static boolean
    DEBUG
    A test client.

  • Constructor Summary

    Constructors
    Constructor
    Description
    MaxPQ()
    Create an empty priority queue.
    MaxPQ(int initCapacity)
    Create an empty priority queue with the given initial capacity.
    MaxPQ(int initCapacity, Comparator<? super K> comparator)
     
    MaxPQ(Comparator<? super K> comparator)
    Create an empty priority queue using the given comparator.
    MaxPQ(K[] keys)
    Create a priority queue with the given items.

  • Method Summary

    Modifier and Type
    Method
    Description
    K
    delMax()
    Delete and return the largest key on the priority queue.
    void
    insert(K x)
    Add a new key to the priority queue.
    boolean
    isEmpty()
    Is the priority queue empty?
    Iterator<K>
    iterator()
    Return an iterator that iterates over all of the keys on the priority queue in descending order.
    static void
    main(String[] args)
     
    K
    max()
    Return the largest key on the priority queue.
    int
    size()
    Return the number of items on the priority queue.

    Methods inherited from class java.lang.Object

    equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator

  • Field Details

    • DEBUG

      public static boolean DEBUG
      A test client.

  • Constructor Details

    • MaxPQ

      public MaxPQ(int initCapacity, Comparator<? super K> comparator)

    • MaxPQ

      public MaxPQ(int initCapacity)
      Create an empty priority queue with the given initial capacity.

    • MaxPQ

      public MaxPQ(Comparator<? super K> comparator)
      Create an empty priority queue using the given comparator.

    • MaxPQ

      public MaxPQ()
      Create an empty priority queue.

    • MaxPQ

      public MaxPQ(K[] keys)
      Create a priority queue with the given items. Takes time proportional to the number of items using sink-based heap construction.

  • Method Details

    • isEmpty

      public boolean isEmpty()
      Is the priority queue empty?

    • size

      public int size()
      Return the number of items on the priority queue.

    • max

      public K max()
      Return the largest key on the priority queue.
      Throws:
      NoSuchElementException - if the priority queue is empty.

    • insert

      public void insert(K x)
      Add a new key to the priority queue.

    • delMax

      public K delMax()
      Delete and return the largest key on the priority queue.
      Throws:
      NoSuchElementException - if the priority queue is empty.

    • iterator

      public Iterator<K> iterator()
      Return an iterator that iterates over all of the keys on the priority queue in descending order.

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

      Specified by:
      iterator in interface Iterable<K extends Comparable<? super K>>

    • main

      public static void main(String[] args)