CSC300 / CSC402: TestPQ [2/7] Previous pageContentsNext page

file:PQ.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
 
package algs24;

// This is a toy interface for Priority Queues
// You are not allowed to insert 0.0
public interface PQ {
  public int size();
  public boolean isEmpty();
  public void insert(double x);
  public double min();
  public double delMin();
  public void toGraphviz();
}

file:TestPQ.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
package algs24;
import java.util.Scanner;
import stdlib.*;

public class TestPQ {
  public static enum Order { INCREASING, DECREASING, RANDOM }
  public static void main(String[] args) {
    show(11, true, "1 4 3 6 8 5 11 10 7 9 2 - - 2"); // Example from text 
    show(9, true, "1 2 3 4 5 6 7 8 9 - - - - - - - -");
    show(9, true, "9 8 7 6 5 4 3 2 1 - - - - - - - -");
    showRandom(10, true);
    double prevInsert = 0;
    double prevDelMin = 0;
    for (int N = 128; N<=MAX; N += N) {
      timeTrial(N, Order.RANDOM);
      StdOut.format("N=%,13d Insert=%7.3f [%8.3f] DelMin=%7.3f [%8.3f]\n", N, timeInsert, timeInsert/prevInsert, timeDelMin, timeDelMin/prevDelMin);
      prevInsert = timeInsert;
      prevDelMin = timeDelMin;
    }
  }
  private static int MAX=200_000;
  private static PQ getPQ (int N) {
    //return new FixedPQSortedIncreasing(N);
    //return new FixedPQSortedDecreasing(N);
    //return new FixedPQUnordered(N);
    MAX=50_000_000; return new FixedPQHeap(N);
  }

  private static double timeInsert;
  private static double timeDelMin;
  private static void timeTrial(int N, Order order) {
    SHOW_STEPS=false;
    PQ pqTime = getPQ(N);       
    Stopwatch sw1 = new Stopwatch();
    for (int i=0; i<N; i+=1) {
      double item = StdRandom.uniform(1,N+1);
      switch (order) {
      case INCREASING: pqTime.insert (i); break; 
      case DECREASING: pqTime.insert(N-i); break; 
      case RANDOM: pqTime.insert (item); break;
      }
    }
    timeInsert = sw1.elapsedTime();

    Stopwatch sw2 = new Stopwatch();    
    for (int i=0; i<N; i+= 1) {
      pqTime.delMin();
    } 
    timeDelMin = sw2.elapsedTime();
  }

  public static boolean SHOW_STEPS=false;
  private static void showRandom (int N, boolean showSteps) {
    SHOW_STEPS=showSteps;
    PQ pq = getPQ(N);
    pq.toGraphviz();
    StdOut.format("               %s\n", pq);
    for (int i=0; i<4*N; i+=1) {
      if (pq.size() > N/2 && (pq.size() == N || StdRandom.random()<.45)) {
        double item = pq.delMin();
        StdOut.format("-%2.0f          : %s\n", item, pq);  
      } else {
        double item = StdRandom.uniform(10,100);
        pq.insert(item);
        StdOut.format("+%2.0f          : %s\n", item, pq);
      }
    }
    StdOut.println();
  }
  private static void show (int N, boolean showSteps, String input) {
    SHOW_STEPS=showSteps;
    Scanner s = new Scanner(input);
    PQ pq = getPQ(N);
    pq.toGraphviz();
    StdOut.format("               %s\n", pq);
    while (s.hasNext()) {
      String next = s.next();
      if ("-".equals(next)) { 
        double item = pq.delMin();
        StdOut.format("-%2.0f          : %s\n", item, pq);
      } else {
        double item = Integer.parseInt(next);
        pq.insert(item);
        StdOut.format("+%2.0f          : %s\n", item, pq);
      }
      pq.toGraphviz();
    }
    StdOut.println();
    s.close();
  }
}

file:FixedPQSortedIncreasing.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
package algs24;
import stdlib.*;
import java.util.Arrays;

public class FixedPQSortedIncreasing implements PQ {
  private int N;
  private double[] a;
  
  public FixedPQSortedIncreasing(int capacity){ N = 0; a = new double[capacity+1]; }  
  public void toGraphviz()          { }
  public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
  public int size()                 { return N; }
  public boolean isEmpty()          { return N == 0; }
  
  public void insert(double x) {
    if (x == 0) throw new Error ("No zeroes allowed");
    if (N >= a.length-1) throw new Error("Overflow");
    N++;
    a[N] = x;
    for (int j = N; j > 1 && a[j] < a[j-1]; j--)
      exch2(j, j-1);
  }
  public double min() {
    return a[1];
  }
  public double delMin() {
    double result = a[1]; 
    for (int j = 2; j <= N; j++)
      exch(j, j-1);
    a[N] = 0.0;
    N--;
    return result;
  }
  private void exch(int i, int j) {
    double oldi = a[i];
    double oldj = a[j];
    a[i] = oldj;
    a[j] = oldi;
    if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
  }
  private void exch2(int i, int j) {
    double oldi = a[i];
    double oldj = a[j];
    if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
    a[i] = oldj;
    a[j] = oldi;
  }
  
  private boolean isSorted() {
    for (int i = 2; i < N; i++)
      if (a[i] < a[i-1]) return false;
    return true;
  }
}

file:FixedPQSortedDecreasing.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
package algs24;
import stdlib.*;
import java.util.Arrays;

public class FixedPQSortedDecreasing implements PQ {
  private int N;
  private double[] a;
  
  public FixedPQSortedDecreasing(int capacity){ N = 0; a = new double[capacity+1]; }  
  public void toGraphviz()          { }
  public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
  public int size()                 { return N; }
  public boolean isEmpty()          { return N == 0; }
  
  public void insert(double x) {
    if (x == 0) throw new Error ("No zeroes allowed");
    if (N >= a.length-1) throw new Error("Overflow");
    N++;
    a[N] = x;
    for (int j = N; j > 1 && a[j] > a[j-1]; j--)
      exch2(j, j-1);
  }
  public double min() {
    return a[N];
  }
  public double delMin() {
    double result = a[N]; 
    a[N] = 0.0;
    N--;
    return result;
  }
  private void exch2(int i, int j) {
    double oldi = a[i];
    double oldj = a[j];
    if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
    a[i] = oldj;
    a[j] = oldi;
  }
}

file:FixedPQUnordered.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
package algs24;
import stdlib.*;
import java.util.Arrays;

public class FixedPQUnordered implements PQ {
  private int N;
  private double[] a;
  
  public FixedPQUnordered(int capacity)  { N = 0; a = new double[capacity+1]; } 
  public void toGraphviz()          { }
  public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
  public int size()                 { return N; }
  public boolean isEmpty()          { return N == 0; }
  
  public void insert(double x) {
    if (x == 0) throw new Error ("No zeroes allowed");
    if (N >= a.length-1) throw new Error("Overflow");
    N++;
    a[N] = x;
  }
  private int minPosition() {
    if (N<=0) throw new Error("Underflow");
    int result = 1;
    for (int i=2; i<=N; i++) 
      if (a[i] < a[result]) result = i;
    return result;
  }
  public double min() {
    int m = minPosition(); 
    return a[m];
  }
  public double delMin() {
    int m = minPosition(); 
    double result = a[m];
    exch2(m, N);
    a[N] = 0.0;
    N--;
    return result;
  }
  private void exch2(int i, int j) {
    double oldi = a[i];
    double oldj = a[j];
    if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
    a[i] = oldj;
    a[j] = oldi;
  }
}

file:FixedPQHeap.java [source]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
package algs24;
import stdlib.*;
import java.util.Arrays;

public class FixedPQHeap implements PQ {
  private int N;
  private double[] a;

  public FixedPQHeap(int capacity)  { N = 0; a = new double[capacity+1]; }  
  public void toGraphviz()          { GraphvizBuilder.binaryHeapToFile (a, N); }
  public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
  public int size()                 { return N; }
  public boolean isEmpty()          { return N == 0; }

  public void insert(double x) {
    if (x == 0) throw new Error ("No zeroes allowed");
    if (N >= a.length-1) throw new Error("Overflow");
    N++;
    a[N] = x;
    swim(N);
  }
  public double min() {
    if (N <= 0) throw new Error("Underflow");
    return a[1];
  }
  public double delMin() {
    double result = min();
    exch(1, N);
    a[N] = 0.0;
    N--;
    sink(1);
    return result;
  }

  private boolean isMinHeap() {
    for (int i = 2; i < N; i++)
      if (a[i] < a[i/2]) return false;
    return true;
  }
  // for comparison:
  private boolean isSorted() {
    for (int i = 2; i < N; i++)
      if (a[i] < a[i-1]) return false;
    return true;
  }

  private void swim(int k) {
    while (k > 1 && a[k/2] > a[k]) {
      int parent = k/2;
      exch2(k, parent);
      k = parent;
    }
  }
  private void sink(int k) {
    while (2*k <= N) {
      int left  = 2*k;
      int right = 2*k + 1;
      int child;
      if (right > N || a[left] < a[right]) 
        child = left;
      else 
        child = right;
      if (a[k] <= a[child]) break;
      exch2(k, child);
      k = child;
    }
  }
  private void sinkFromSlides(int k) {                
    while (2*k <= N) {                      
      int child = 2*k;                      
      if (2*k < N && a[2*k] > a[2*k+1])  
        child = 2*k + 1;
      if (a[k] <= a[child]) break;    
      exch2(k, child);                                    
      k = child;                                          
    }
    if (!isMinHeap()) throw new Error();
  }    
  private void exch(int i, int j) {
    double oldi = a[i];
    double oldj = a[j];
    a[i] = oldj;
    a[j] = oldi;
    if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
  }
  private void exch2(int i, int j) {
    double oldi = a[i];
    double oldj = a[j];
    if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
    a[i] = oldj;
    a[j] = oldi;
  }
}

Previous pageContentsNext page