SHARE
TWEET

Untitled

a guest Jul 20th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. private static class PQKey {
  2.         double price;
  3.         int stopsFromSource;
  4.         public PQKey(double price, int stopsFromSource) {
  5.             this.price = price;
  6.             this.stopsFromSource = stopsFromSource;
  7.         }
  8.     }
  9.    
  10.     private static class IndexMinPQ {
  11.        
  12.         private int maxSize;
  13.         private int[] pq; //holds index at each size of pq;
  14.         private int[] qp; //the inverse of pq, holds the size at each index of the input
  15.         private PQKey[] keys; //these are the values by which we are going to sort PQ
  16.         private int n; //current size of the pq
  17.        
  18.         public IndexMinPQ(int capacity) {
  19.             this.maxSize = capacity;
  20.             this.keys = new PQKey[maxSize];
  21.             this.pq = new int[maxSize+1]; // +1 because the index is size
  22.             this.qp = new int[maxSize];
  23.            
  24.             for(int i=0; i < maxSize; i++)
  25.                 qp[i] = -1;
  26.            
  27.         }
  28.        
  29.         public boolean containsKey(int k) {
  30.             return qp[k] != -1;
  31.         }
  32.        
  33.         public boolean isEmpty() {
  34.             return n == 0;
  35.         }
  36.        
  37.        
  38.         public void insert(int i, PQKey key) {
  39.             n++;
  40.             this.qp[i] = n;
  41.             this.pq[n] = i;
  42.             this.keys[i] = key;
  43.             //System.out.println("i --> " + i + ", n --> " + n + ", i --> " + i);
  44.             swim(n);
  45.         }
  46.        
  47.        
  48.         public int[] deleteMin() {
  49.             int[] result = new int[2];
  50.            
  51.             int min = pq[1];
  52.             result[0] = min;
  53.            
  54.             exch(1,n--);
  55.             sink(1);
  56.             qp[min] = -1;
  57.            
  58.             result[1] = keys[min].stopsFromSource;
  59.            
  60.             keys[min] = null;
  61.            
  62.             return result;
  63.         }
  64.        
  65.         public int[] peek() {
  66.              int[] result = new int[2];
  67.            
  68.               int min = pq[1];
  69.               result[0] = min;
  70.               result[1] = keys[min].stopsFromSource;
  71.            
  72.               return result;
  73.         }
  74.        
  75.        
  76.         public void decreaseKey(int i, PQKey key) {
  77.             this.keys[i] = key;            
  78.             swim(qp[i]);
  79.         }
  80.        
  81.         private void swim(int k) {
  82.            
  83.             while(k > 1 && greater(k/2,k)) {
  84.                 exch(k/2,k);
  85.                 k = k/2;
  86.             }
  87.            
  88.         }
  89.        
  90.        
  91.         private void sink(int k) {
  92.             while(2*k <= n) {
  93.                 int j = 2*k;
  94.                 if(j < n && greater(j,j+1)) j++;
  95.                 if(!greater(k,j)) break;
  96.                 exch(k,j);
  97.                 k = j; //this is very important, it is not k = 2*k;
  98.             }
  99.         }
  100.        
  101.         private void exch(int i, int j) {
  102.            
  103.             //i and j are sizes
  104.             //since pq holds holds the size as index
  105.             //exchange pq first
  106.            
  107.             int swap = pq[i];
  108.             pq[i] = pq[j];
  109.             pq[j] = swap;
  110.            
  111.             //now exchange corresponding indexes in qp array
  112.            
  113.             qp[pq[i]] = i; //notice i --> i correspondence, its because pq[i]  has the correct index that needs to change is'v alue
  114.             qp[pq[j]] = j; //notice j --> j correspondence
  115.        
  116.            
  117.            
  118.         }
  119.        
  120.         private boolean greater(int i, int j) {
  121.             //System.out.println("i --> " + i + ", j --> " + j + ", n --> " + n);
  122.  
  123.             return keys[pq[i]].price-keys[pq[j]].price > 0 ? true: false;
  124.         }
  125.        
  126.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top