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}