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}