001package algs24;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Heap.java
005 *  Execution:    java Heap < input.txt
006 *  Dependencies: StdOut.java StdIn.java
007 *  Data files:   http://algs4.cs.princeton.edu/24pq/tiny.txt
008 *                http://algs4.cs.princeton.edu/24pq/words3.txt
009 *
010 *  Sorts a sequence of strings from standard input using heapsort.
011 *
012 *  % more tiny.txt
013 *  S O R T E X A M P L E
014 *
015 *  % java Heap < tiny.txt
016 *  A E E L M O P R S T X                 [ one string per line ]
017 *
018 *  % more words3.txt
019 *  bed bug dad yes zoo ... all bad yet
020 *
021 *  % java Heap < words3.txt
022 *  all bad bed bug dad ... yes yet zoo   [ one string per line ]
023 *
024 *************************************************************************/
025
026public class Heap {
027
028        public static <T extends Comparable<? super T>> void sort(T[] pq) {
029                int N = pq.length;
030                for (int k = N/2; k >= 1; k--) {
031                        sink(pq, k, N);
032                }
033                while (N > 1) {
034                        exch(pq, 1, N);
035                        N--;
036                        sink(pq, 1, N);
037                }
038        }
039
040        /* *********************************************************************
041         * Helper functions to restore the heap invariant.
042         **********************************************************************/
043
044        private static <T extends Comparable<? super T>> void sink(T[] pq, int k, int N) {
045                while (2*k <= N) {
046                        int j = 2*k;
047                        if (j < N && less(pq, j, j+1)) j++;
048                        if (!less(pq, k, j)) break;
049                        exch(pq, k, j);
050                        k = j;
051                }
052        }
053
054        /* *********************************************************************
055         * Helper functions for comparisons and swaps.
056         * Indices are "off-by-one" to support 1-based indexing.
057         **********************************************************************/
058        private static <T extends Comparable<? super T>> boolean less(T[] pq, int i, int j) {
059                if (COUNT_OPS) DoublingTest.incOps ();
060                return pq[i-1].compareTo(pq[j-1]) < 0;
061        }
062
063        private static <T> void exch(T[] pq, int i, int j) {
064                if (COUNT_OPS) DoublingTest.incOps ();
065                T swap = pq[i-1];
066                pq[i-1] = pq[j-1];
067                pq[j-1] = swap;
068        }
069
070        // is v < w ?
071        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
072                if (COUNT_OPS) DoublingTest.incOps ();
073                return (v.compareTo(w) < 0);
074        }
075
076
077        /* *********************************************************************
078         *  Check if array is sorted - useful for debugging
079         ***********************************************************************/
080        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
081                for (int i = 1; i < a.length; i++)
082                        if (less(a[i], a[i-1])) return false;
083                return true;
084        }
085
086
087        // print array to standard output
088        private static <T> void show(T[] a) {
089                for (T element : a) {
090                        StdOut.println(element);
091                }
092        }
093
094
095        // test code
096        private static boolean COUNT_OPS = false;
097        public static void main(String[] args) {
098                StdIn.fromString ("S O R T E X A M P L E");
099                //StdIn.fromFile ("data/tiny.txt");
100                //StdIn.fromFile ("data/cards.txt");
101                //StdIn.fromFile ("data/words3.txt");
102
103                String[] a = StdIn.readAllStrings();
104                //StdRandom.shuffle (a);
105                //show(a);
106                //StdOut.println ("----------------");
107                sort(a);
108                show(a);
109
110                COUNT_OPS = true;
111                DoublingTest.run (2000, 10, N -> ArrayGenerator.integerRandomUnique (N),          (Integer[] x) -> sort (x));
112                //DoublingTest.run (2000, 10, N -> ArrayGenerator.integerRandom (N, 2),             (Integer[] x) -> sort (x));
113                //DoublingTest.run (2000, 10, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x));
114        }
115}