001package algs24; 002import java.util.Scanner; 003import stdlib.*; 004 005public class TestPQ { 006 public static enum Order { INCREASING, DECREASING, RANDOM } 007 public static void main(String[] args) { 008 show(11, true, "1 4 3 6 8 5 11 10 7 9 2 - - 2"); // Example from text 009 show(9, true, "1 2 3 4 5 6 7 8 9 - - - - - - - -"); 010 show(9, true, "9 8 7 6 5 4 3 2 1 - - - - - - - -"); 011 showRandom(10, true); 012 double prevInsert = 0; 013 double prevDelMin = 0; 014 for (int N = 128; N<=MAX; N += N) { 015 timeTrial(N, Order.RANDOM); 016 StdOut.format("N=%,13d Insert=%7.3f [%8.3f] DelMin=%7.3f [%8.3f]\n", N, timeInsert, timeInsert/prevInsert, timeDelMin, timeDelMin/prevDelMin); 017 prevInsert = timeInsert; 018 prevDelMin = timeDelMin; 019 } 020 } 021 private static int MAX=200_000; 022 private static PQ getPQ (int N) { 023 //return new FixedPQSortedIncreasing(N); 024 //return new FixedPQSortedDecreasing(N); 025 //return new FixedPQUnordered(N); 026 MAX=50_000_000; return new FixedPQHeap(N); 027 } 028 029 private static double timeInsert; 030 private static double timeDelMin; 031 private static void timeTrial(int N, Order order) { 032 SHOW_STEPS=false; 033 PQ pqTime = getPQ(N); 034 Stopwatch sw1 = new Stopwatch(); 035 for (int i=0; i<N; i+=1) { 036 double item = StdRandom.uniform(1,N+1); 037 switch (order) { 038 case INCREASING: pqTime.insert (i); break; 039 case DECREASING: pqTime.insert(N-i); break; 040 case RANDOM: pqTime.insert (item); break; 041 } 042 } 043 timeInsert = sw1.elapsedTime(); 044 045 Stopwatch sw2 = new Stopwatch(); 046 for (int i=0; i<N; i+= 1) { 047 pqTime.delMin(); 048 } 049 timeDelMin = sw2.elapsedTime(); 050 } 051 052 public static boolean SHOW_STEPS=false; 053 private static void showRandom (int N, boolean showSteps) { 054 SHOW_STEPS=showSteps; 055 PQ pq = getPQ(N); 056 pq.toGraphviz(); 057 StdOut.format(" %s\n", pq); 058 for (int i=0; i<4*N; i+=1) { 059 if (pq.size() > N/2 && (pq.size() == N || StdRandom.random()<.45)) { 060 double item = pq.delMin(); 061 StdOut.format("-%2.0f : %s\n", item, pq); 062 } else { 063 double item = StdRandom.uniform(10,100); 064 pq.insert(item); 065 StdOut.format("+%2.0f : %s\n", item, pq); 066 } 067 } 068 StdOut.println(); 069 } 070 private static void show (int N, boolean showSteps, String input) { 071 SHOW_STEPS=showSteps; 072 Scanner s = new Scanner(input); 073 PQ pq = getPQ(N); 074 pq.toGraphviz(); 075 StdOut.format(" %s\n", pq); 076 while (s.hasNext()) { 077 String next = s.next(); 078 if ("-".equals(next)) { 079 double item = pq.delMin(); 080 StdOut.format("-%2.0f : %s\n", item, pq); 081 } else { 082 double item = Integer.parseInt(next); 083 pq.insert(item); 084 StdOut.format("+%2.0f : %s\n", item, pq); 085 } 086 pq.toGraphviz(); 087 } 088 StdOut.println(); 089 s.close(); 090 } 091}