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;
  }
}