Priority queue

In the package algs24, you will find a class MinPQ, which implements a minimum priority queue. You are to use it to define in the Final class a generic sort method with the signature:

 public static > void minpqSort(Item[] a) 

The code in the method should:

Create a MinPQ object. This class implements a minimum priority queue and is found in the algs24 package.

Insert each value in the parameter array into the min priority queue.

Using the delMin method, remove values from the min priority queue and place them into the array, overwriting the values that were there.

Done correctly, the array will now be sorted in ascending order.

FIFO Queue

Define in the Final class a generic method called reverseQueue with the signature:

public static Queue reverseQueue(Queue queue) 

It modifies its parameter so that, when it returns, the values in the queue are reversed. For example, if the queue q1 contains the integer values 13, 15, 9, 10, and 25 (in that order), the following call:

q2 = reverseQueue(q1); 

will result in q2 having the values 25, 10, 9, 15, 13 (in that order).

Use the queue class defined in algs13.

Pakage 24;

package algs24; import stdlib.*; import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac MinPQ.java * Execution: java MinPQ < input.txt * * Generic min priority queue implementation with a binary heap. * Can be used with a comparator instead of the natural order, * but the generic key type must still be Comparable. * * % java MinPQ < tinyPQ.txt * E A E (6 left on pq) * * We use a one-based array to simplify parent and child calculations. * *************************************************************************/

/** * 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. */ public class MinPQ> implements Iterable { private K[] pq; // store items at indices 1 to N private int N; // number of items on priority queue private Comparator comparator; // optional comparator

// helper function to double the size of the heap array @SuppressWarnings("unchecked") private void resize(int capacity) { if (capacity <= N) throw new IllegalArgumentException (); K[] temp = (K[]) new Comparable[capacity]; for (int i = 1; i <= N; i++) temp[i] = pq[i]; pq = temp; }

@SuppressWarnings("unchecked") /** Create an empty priority queue with the given initial capacity, using the given comparator. */ public MinPQ(int initCapacity, Comparator comparator) { pq = (K[]) new Comparable[initCapacity + 1]; N = 0; this.comparator = comparator; } /** Create an empty priority queue with the given initial capacity. */ public MinPQ(int initCapacity) { this(initCapacity, null); } /** Create an empty priority queue using the given comparator. */ public MinPQ(Comparator comparator) { this(1, comparator); } /** Create an empty priority queue. */ public MinPQ() { this(1, null); }

/** * Create a priority queue with the given items. * Takes time proportional to the number of items using sink-based heap construction. */ public MinPQ(K[] keys) { this(keys.length, null); N = keys.length; for (int i = 0; i < N; i++) pq[i+1] = keys[i]; for (int k = N/2; k >= 1; k--) sink(k); //assert isMinHeap(); }

/** Is the priority queue empty? */ public boolean isEmpty() { return N == 0; }

/** Return the number of items on the priority queue. */ public int size() { return N; }

/** * Return the smallest key on the priority queue. * @throws java.util.NoSuchElementException if the priority queue is empty. */ public K min() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; }

/** Add a new key to the priority queue. */ public void insert(K 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(); }

/** * Delete and return the smallest key on the priority queue. * @throws java.util.NoSuchElementException if the priority queue is empty. */ public K delMin() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); exch(1, N); K min = pq[N--]; sink(1); pq[N+1] = null; // 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, k/2); 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 pq[i].compareTo(pq[j]) > 0; } else { return comparator.compare(pq[i], pq[j]) > 0; } }

private void exch(int i, int j) { K swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; }

// is pq[1..N] a min heap? private boolean isMinHeap() { return isMinHeap(1); }

// is subtree of pq[1..N] rooted at k a min heap? private boolean isMinHeap(int k) { if (k > N) return true; int left = 2*k, right = 2*k + 1; if (left <= N && greater(k, left)) return false; if (right <= N && greater(k, right)) return false; return isMinHeap(left) && isMinHeap(right); }

/* ********************************************************************* * 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. */ public Iterator iterator() { return new HeapIterator(); }

private class HeapIterator implements Iterator { // create a new pq private MinPQ 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(size()); else copy = new MinPQ(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 K next() { if (!hasNext()) throw new NoSuchElementException(); return copy.delMin(); } }

void showHeap() { for (int i = 1; i <= N; i++) StdOut.print (pq[i] + " "); StdOut.println (); }

/** * A test client. */ public static void main(String[] args) { MinPQ pq = new MinPQ<>(100); StdIn.fromString ("10 20 30 40 50 - - - 05 25 35 - - - 70 80 05 - - - - "); while (!StdIn.isEmpty()) { StdOut.print ("pq: "); pq.showHeap(); String item = StdIn.readString(); if (item.equals("-")) StdOut.println("min: " + pq.delMin()); else pq.insert(item); GraphvizBuilder.binaryHeapToFile (pq.pq, pq.N); } StdOut.println("(" + pq.size() + " left on pq)"); }

}

Package Algs 13;

package algs13; import stdlib.*; import java.util.Iterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac Queue.java * Execution: java Queue < input.txt * Data files: http://algs4.cs.princeton.edu/13stacks/tobe.txt * * A generic queue, implemented using a linked list. * * % java Queue < tobe.txt * to be or not to be (2 left on queue) * *************************************************************************/ /** * The Queue class represents a first-in-first-out (FIFO) * queue of generic items. * It supports the usual enqueue and dequeue * operations, along with methods for peeking at the top item, * testing if the queue is empty, and iterating through * the items in FIFO order. *

* All queue operations except iteration are constant time. *

* For additional documentation, see Section 1.3 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class Queue implements Iterable { private int N; // number of elements on queue private Node first; // beginning of queue private Node last; // end of queue

// helper linked list class private static class Node { public Node() { } public T item; public Node next; }

/** * Create an empty queue. */ public Queue() { first = null; last = null; N = 0; }

/** * Is the queue empty? */ public boolean isEmpty() { return first == null; }

/** * Return the number of items in the queue. */ public int size() { return N; }

/** * Return the item least recently added to the queue. * @throws java.util.NoSuchElementException if queue is empty. */ public T peek() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); return first.item; }

/** * Add the item to the queue. */ public void enqueue(T item) { Node oldlast = last; last = new Node<>(); last.item = item; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; N++; }

/** * Remove and return the item on the queue least recently added. * @throws java.util.NoSuchElementException if queue is empty. */ public T dequeue() { if (isEmpty()) throw new NoSuchElementException("Queue underflow"); T item = first.item; first = first.next; N--; if (isEmpty()) last = null; return item; }

/** * Return string representation. */ public String toString() { StringBuilder s = new StringBuilder(); for (T item : this) s.append(item + " "); return s.toString(); }

// check internal invariants private static boolean check(Queue that) { int N = that.N; Queue.Node first = that.first; Queue.Node last = that.last; if (N == 0) { if (first != null) return false; if (last != null) return false; } else if (N == 1) { if (first == null || last == null) return false; if (first != last) return false; if (first.next != null) return false; } else { if (first == last) return false; if (first.next == null) return false; if (last.next != null) return false;

// check internal consistency of instance variable N int numberOfNodes = 0; for (Queue.Node x = first; x != null; x = x.next) { numberOfNodes++; } if (numberOfNodes != N) return false;

// check internal consistency of instance variable last Queue.Node lastNode = first; while (lastNode.next != null) { lastNode = lastNode.next; } if (last != lastNode) return false; }

return true; }

/** * Return an iterator that iterates over the items on the queue in FIFO order. */ public Iterator iterator() { return new ListIterator(); }

// an iterator, doesn't implement remove() since it's optional private class ListIterator implements Iterator { private Node current = first;

public boolean hasNext() { return current != null; } public void remove() { throw new UnsupportedOperationException(); }

public T next() { if (!hasNext()) throw new NoSuchElementException(); T item = current.item; current = current.next; return item; } }

public void toGraphviz(String filename) { GraphvizBuilder gb = new GraphvizBuilder (); toGraphviz (gb, null, first); gb.toFile (filename, "rankdir=\"LR\""); } private void toGraphviz (GraphvizBuilder gb, Node prev, Node n) { if (n == null) { gb.addNullEdge (prev); return; } gb.addLabeledNode (n, n.item.toString ()); if (prev != null) gb.addEdge (prev, n); toGraphviz (gb, n, n.next); }

/** * A test client. */ public static void main(String[] args) { StdIn.fromString ("to be or not to - be - - that - - - is"); Queue q = new Queue<>(); int count = 0; q.toGraphviz ("queue" + count + ".png"); count++; while (!StdIn.isEmpty()) { String item = StdIn.readString(); if (!item.equals("-")) q.enqueue(item); else if (!q.isEmpty()) StdOut.print(q.dequeue() + " "); q.toGraphviz ("queue" + count + ".png"); count++; } StdOut.println("(" + q.size() + " left on queue)"); } }