Below is the syntax highlighted version of MinPQ.java.
/****************************************************************************** * Compilation: javac MinPQ.java * Execution: java MinPQ < input.txt * Dependencies: StdIn.java StdOut.java * Data files: https://algs4.cs.princeton.edu/24pq/tinyPQ.txt * * Generic min priority queue implementation with a binary heap. * Can be used with a comparator instead of the natural order. * * % java MinPQ < tinyPQ.txt * E A E (6 left on pq) * * We use a one-based array to simplify parent and child calculations. * * Can be optimized by replacing full exchanges with half exchanges * (ala insertion sort). * ******************************************************************************/ package edu.princeton.cs.algs4; import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; /** * The {@code MinPQ} class represents a priority queue of generic keys. * It supports the usual <em>insert</em> and <em>delete-the-minimum</em> * operations, along with methods for peeking at the minimum key, * testing if the priority queue is empty, and iterating through * the keys. * <p> * This implementation uses a <em>binary heap</em>. * The <em>insert</em> and <em>delete-the-minimum</em> operations take * Θ(log <em>n</em>) amortized time, where <em>n</em> 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 <em>min</em>, <em>size</em>, and <em>is-empty</em> 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. * <p> * For additional documentation, see * <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne * * @param <Key> the generic type of key on this priority queue */ public class MinPQ<Key> implements Iterable<Key> { private Key[] pq; // store items at indices 1 to n private int n; // number of items on priority queue private Comparator<Key> comparator; // optional comparator /** * Initializes an empty priority queue with the given initial capacity. * * @param initCapacity the initial capacity of this priority queue */ public MinPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; n = 0; } /** * Initializes an empty priority queue. */ public MinPQ() { this(1); } /** * Initializes an empty priority queue with the given initial capacity, * using the given comparator. * * @param initCapacity the initial capacity of this priority queue * @param comparator the order in which to compare the keys */ public MinPQ(int initCapacity, Comparator<Key> comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; n = 0; } /** * Initializes an empty priority queue using the given comparator. * * @param comparator the order in which to compare the keys */ public MinPQ(Comparator<Key> comparator) { this(1, comparator); } /** * Initializes a priority queue from the array of keys. * <p> * Takes time proportional to the number of keys, using sink-based heap construction. * * @param keys the array of keys */ public MinPQ(Key[] keys) { n = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i < n; i++) pq[i+1] = keys[i]; for (int k = n/2; k >= 1; k--) sink(k); assert isMinHeap(); } /** * Returns true if this priority queue is empty. * * @return {@code true} if this priority queue is empty; * {@code false} otherwise */ public boolean isEmpty() { return n == 0; } /** * Returns the number of keys on this priority queue. * * @return the number of keys on this priority queue */ public int size() { return n; } /** * Returns a smallest key on this priority queue. * * @return a smallest key on this priority queue * @throws NoSuchElementException if this priority queue is empty */ public Key min() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // resize the underlying array to have the given capacity private void resize(int capacity) { assert capacity > n; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i <= n; i++) { temp[i] = pq[i]; } pq = temp; } /** * Adds a new key to this priority queue. * * @param x the key to add to this priority queue */ public void insert(Key x) { // double size of array if necessary if (n == pq.length - 1) resize(2 * pq.length); // add x, and percolate it up to maintain heap invariant pq[++n] = x; swim(n); assert isMinHeap(); } /** * Removes and returns a smallest key on this priority queue. * * @return a smallest key on this priority queue * @throws NoSuchElementException if this priority queue is empty */ public Key delMin() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); Key min = pq[1]; exch(1, n--); sink(1); pq[n+1] = null; // to avoid loitering and help with garbage collection if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMinHeap(); return min; } /*************************************************************************** * Helper functions to restore the heap invariant. ***************************************************************************/ private void swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k/2, k); k = k/2; } } private void sink(int k) { while (2*k <= n) { int j = 2*k; if (j < n && greater(j, j+1)) j++; if (!greater(k, j)) break; exch(k, j); k = j; } } /*************************************************************************** * Helper functions for compares and swaps. ***************************************************************************/ private boolean greater(int i, int j) { if (comparator == null) { return ((Comparable<Key>) pq[i]).compareTo(pq[j]) > 0; } else { return comparator.compare(pq[i], pq[j]) > 0; } } private void exch(int i, int j) { Key swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; } // is pq[1..n] a min heap? private boolean isMinHeap() { for (int i = 1; i <= n; i++) { if (pq[i] == null) return false; } for (int i = n+1; i < pq.length; i++) { if (pq[i] != null) return false; } if (pq[0] != null) return false; return isMinHeapOrdered(1); } // is subtree of pq[1..n] rooted at k a min heap? private boolean isMinHeapOrdered(int k) { if (k > n) return true; int left = 2*k; int right = 2*k + 1; if (left <= n && greater(k, left)) return false; if (right <= n && greater(k, right)) return false; return isMinHeapOrdered(left) && isMinHeapOrdered(right); } /** * Returns an iterator that iterates over the keys on this priority queue * in ascending order. * <p> * The iterator doesn't implement {@code remove()} since it's optional. * * @return an iterator that iterates over the keys in ascending order */ public Iterator<Key> iterator() { return new HeapIterator(); } private class HeapIterator implements Iterator<Key> { // create a new pq private MinPQ<Key> copy; // add all items to copy of heap // takes linear time since already in heap order so no keys move public HeapIterator() { if (comparator == null) copy = new MinPQ<Key>(size()); else copy = new MinPQ<Key>(size(), comparator); for (int i = 1; i <= n; i++) copy.insert(pq[i]); } public boolean hasNext() { return !copy.isEmpty(); } public void remove() { throw new UnsupportedOperationException(); } public Key next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMin(); } } /** * Unit tests the {@code MinPQ} data type. * * @param args the command-line arguments */ public static void main(String[] args) { MinPQ<String> pq = new MinPQ<String>(); while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) pq.insert(item); else if (!pq.isEmpty()) StdOut.print(pq.delMin() + " "); } StdOut.println("(" + pq.size() + " left on pq)"); } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/