Package algs24

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

java.lang.Object
algs24.MinPQ<K>
All Implemented Interfaces:
Iterable<K>

public class MinPQ<K extends Comparable<? super K>> extends Object implements Iterable<K>
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 maximum key, testing if the priority queue is empty, and iterating through the keys.

The insert and delete-the-minimum operations take logarithmic amortized time. The min, 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.

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private class 
     
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private Comparator<? super K>
     
    static boolean
    A test client.
    private int
     
    private K[]
     
  • Constructor Summary

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

    Modifier and Type
    Method
    Description
    Delete and return the smallest key on the priority queue.
    private void
    exch(int i, int j)
     
    private boolean
    greater(int i, int j)
     
    void
    insert(K x)
    Add a new key to the priority queue.
    boolean
    Is the priority queue empty?
    private boolean
     
    private boolean
    isMinHeap(int k)
     
    Return an iterator that iterates over all of the keys on the priority queue in ascending order.
    static void
    main(String[] args)
     
    min()
    Return the smallest key on the priority queue.
    private void
    resize(int capacity)
     
    (package private) void
     
    private void
    sink(int k)
     
    int
    Return the number of items on the priority queue.
    private void
    swim(int k)
     

    Methods inherited from class java.lang.Object

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

    Methods inherited from interface java.lang.Iterable

    forEach, spliterator
  • Field Details

  • Constructor Details

    • MinPQ

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

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

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

      public MinPQ()
      Create an empty priority queue.
    • MinPQ

      public MinPQ(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

    • resize

      private void resize(int capacity)
    • isEmpty

      public boolean isEmpty()
      Is the priority queue empty?
    • size

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

      public K min()
      Return the smallest 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.
    • delMin

      public K delMin()
      Delete and return the smallest key on the priority queue.
      Throws:
      NoSuchElementException - if the priority queue is empty.
    • swim

      private void swim(int k)
    • sink

      private void sink(int k)
    • greater

      private boolean greater(int i, int j)
    • exch

      private void exch(int i, int j)
    • isMinHeap

      private boolean isMinHeap()
    • isMinHeap

      private boolean isMinHeap(int k)
    • iterator

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

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

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

      void showHeap()
    • main

      public static void main(String[] args)