001package algs24;
002import stdlib.*;
003import java.util.Arrays;
004
005public class FixedPQHeap implements PQ {
006        private int N;
007        private double[] a;
008        
009        public FixedPQHeap(int capacity)  { N = 0; a = new double[capacity+1]; }        
010        public void toGraphviz()          { GraphvizBuilder.binaryHeapToFile (a, N); }
011        public String toString ()         { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
012        public int size()                 { return N; }
013        public boolean isEmpty()          { return N == 0; }
014        
015        public void insert(double x) {
016                if (x == 0) throw new Error ("No zeroes allowed");
017                if (N >= a.length-1) throw new Error("Overflow");
018                N++;
019                a[N] = x;
020                swim(N);
021        }
022        public double min() {
023                if (N <= 0) throw new Error("Underflow");
024                return a[1];
025        }
026        public double delMin() {
027                double result = min();
028                exch(1, N);
029                a[N] = 0.0;
030                N--;
031                sink(1);
032                return result;
033        }
034
035        private boolean isMinHeap() {
036                for (int i = 2; i < N; i++)
037                        if (a[i] < a[i/2]) return false;
038                return true;
039        }
040        // for comparison:
041        private boolean isSorted() {
042                for (int i = 2; i < N; i++)
043                        if (a[i] < a[i-1]) return false;
044                return true;
045        }
046        
047        private void swim(int k) {
048                while (k > 1 && a[k/2] > a[k]) {
049                        int parent = k/2;
050                        exch2(k, parent);
051                        k = parent;
052                }
053        }
054        private void sink(int k) {
055                while (2*k <= N) {
056                        int left  = 2*k;
057                        int right = 2*k + 1;
058                        int champ;
059                        if (right > N || a[left] < a[right]) 
060                                champ = left;
061                        else 
062                                champ = right;
063                        if (a[k] < a[champ]) break;
064                        exch2(k, champ);
065                        k = champ;
066                }
067        }
068        private void exch(int i, int j) {
069                double oldi = a[i];
070                double oldj = a[j];
071                a[i] = oldj;
072                a[j] = oldi;
073                if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
074        }
075        private void exch2(int i, int j) {
076                double oldi = a[i];
077                double oldj = a[j];
078                if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
079                a[i] = oldj;
080                a[j] = oldi;
081        }
082}