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 child;
059                        if (right > N || a[left] < a[right]) 
060                                child = left;
061                        else 
062                                child = right;
063                        if (a[k] <= a[child]) break;
064                        exch2(k, child);
065                        k = child;
066                }
067        }
068        private void sinkFromSlides(int k) {                
069                while (2*k <= N) {                      
070                        int child = 2*k;                      
071                        if (2*k < N && a[2*k] > a[2*k+1])  
072                                child = 2*k + 1;
073                        if (a[k] <= a[child]) break;    
074                        exch2(k, child);                                    
075                        k = child;                                          
076                }
077                if (!isMinHeap()) throw new Error();
078        }    
079        private void exch(int i, int j) {
080                double oldi = a[i];
081                double oldj = a[j];
082                a[i] = oldj;
083                a[j] = oldi;
084                if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
085        }
086        private void exch2(int i, int j) {
087                double oldi = a[i];
088                double oldj = a[j];
089                if (TestPQ.SHOW_STEPS) { StdOut.format("  exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
090                a[i] = oldj;
091                a[j] = oldi;
092        }
093}