CSC300 / CSC402: FixedPQSortedDecreasing [4/7] Previous pageContentsNext page

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
  public void insert(double x) {
    N++;
    a[N] = x;
    for (int j = N; j > 1 && a[j] > a[j-1]; j--)
      exch(j, j-1);
  }
  public double delMin() {
    double result = a[N]; 


    a[N] = 0.0;
    N--;

    return result;
  }

Output

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
+ 4          : [ , 4, 1, , , , , , , , , ]
+ 3          : [ , 4, 3, 1, , , , , , , , ]
+ 6          : [ , 6, 4, 3, 1, , , , , , , ]
+ 8          : [ , 8, 6, 4, 3, 1, , , , , , ]
+ 5          : [ , 8, 6, 5, 4, 3, 1, , , , , ]
+11          : [ , 11, 8, 6, 5, 4, 3, 1, , , , ]
+10          : [ , 11, 10, 8, 6, 5, 4, 3, 1, , , ]
+ 7          : [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, , ]
+ 9          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, ]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
- 1          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]
- 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, , ]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]        

N=          128 Insert=  0.012 [Infinity] DelMin=  0.000 [     NaN]
N=          256 Insert=  0.008 [   0.667] DelMin=  0.000 [     NaN]
N=          512 Insert=  0.003 [   0.375] DelMin=  0.000 [     NaN]
N=        1,024 Insert=  0.032 [  10.667] DelMin=  0.001 [Infinity]
N=        2,048 Insert=  0.007 [   0.219] DelMin=  0.000 [   0.000]
N=        4,096 Insert=  0.015 [   2.143] DelMin=  0.000 [     NaN]
N=        8,192 Insert=  0.051 [   3.400] DelMin=  0.000 [     NaN]
N=       16,384 Insert=  0.138 [   2.706] DelMin=  0.000 [     NaN]
N=       32,768 Insert=  0.372 [   2.696] DelMin=  0.000 [     NaN]
N=       65,536 Insert=  1.359 [   3.653] DelMin=  0.000 [     NaN]
N=      131,072 Insert=  4.550 [   3.348] DelMin=  0.000 [     NaN]

Insert is linear, DeleteMin is constant

               [ , , , , , , , , , , , ]
+ 1          : [ , 1, , , , , , , , , , ]
  exch( 4, 1)> [ , 1, 4, , , , , , , , , ]
+ 4          : [ , 4, 1, , , , , , , , , ]
  exch( 3, 1)> [ , 4, 1, 3, , , , , , , , ]
+ 3          : [ , 4, 3, 1, , , , , , , , ]
  exch( 6, 1)> [ , 4, 3, 1, 6, , , , , , , ]
  exch( 6, 3)> [ , 4, 3, 6, 1, , , , , , , ]
  exch( 6, 4)> [ , 4, 6, 3, 1, , , , , , , ]
+ 6          : [ , 6, 4, 3, 1, , , , , , , ]
  exch( 8, 1)> [ , 6, 4, 3, 1, 8, , , , , , ]
  exch( 8, 3)> [ , 6, 4, 3, 8, 1, , , , , , ]
  exch( 8, 4)> [ , 6, 4, 8, 3, 1, , , , , , ]
  exch( 8, 6)> [ , 6, 8, 4, 3, 1, , , , , , ]
+ 8          : [ , 8, 6, 4, 3, 1, , , , , , ]
  exch( 5, 1)> [ , 8, 6, 4, 3, 1, 5, , , , , ]
  exch( 5, 3)> [ , 8, 6, 4, 3, 5, 1, , , , , ]
  exch( 5, 4)> [ , 8, 6, 4, 5, 3, 1, , , , , ]
+ 5          : [ , 8, 6, 5, 4, 3, 1, , , , , ]
  exch(11, 1)> [ , 8, 6, 5, 4, 3, 1, 11, , , , ]
  exch(11, 3)> [ , 8, 6, 5, 4, 3, 11, 1, , , , ]
  exch(11, 4)> [ , 8, 6, 5, 4, 11, 3, 1, , , , ]
  exch(11, 5)> [ , 8, 6, 5, 11, 4, 3, 1, , , , ]
  exch(11, 6)> [ , 8, 6, 11, 5, 4, 3, 1, , , , ]
  exch(11, 8)> [ , 8, 11, 6, 5, 4, 3, 1, , , , ]
+11          : [ , 11, 8, 6, 5, 4, 3, 1, , , , ]
  exch(10, 1)> [ , 11, 8, 6, 5, 4, 3, 1, 10, , , ]
  exch(10, 3)> [ , 11, 8, 6, 5, 4, 3, 10, 1, , , ]
  exch(10, 4)> [ , 11, 8, 6, 5, 4, 10, 3, 1, , , ]
  exch(10, 5)> [ , 11, 8, 6, 5, 10, 4, 3, 1, , , ]
  exch(10, 6)> [ , 11, 8, 6, 10, 5, 4, 3, 1, , , ]
  exch(10, 8)> [ , 11, 8, 10, 6, 5, 4, 3, 1, , , ]
+10          : [ , 11, 10, 8, 6, 5, 4, 3, 1, , , ]
  exch( 7, 1)> [ , 11, 10, 8, 6, 5, 4, 3, 1, 7, , ]
  exch( 7, 3)> [ , 11, 10, 8, 6, 5, 4, 3, 7, 1, , ]
  exch( 7, 4)> [ , 11, 10, 8, 6, 5, 4, 7, 3, 1, , ]
  exch( 7, 5)> [ , 11, 10, 8, 6, 5, 7, 4, 3, 1, , ]
  exch( 7, 6)> [ , 11, 10, 8, 6, 7, 5, 4, 3, 1, , ]
+ 7          : [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, , ]
  exch( 9, 1)> [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, 9, ]
  exch( 9, 3)> [ , 11, 10, 8, 7, 6, 5, 4, 3, 9, 1, ]
  exch( 9, 4)> [ , 11, 10, 8, 7, 6, 5, 4, 9, 3, 1, ]
  exch( 9, 5)> [ , 11, 10, 8, 7, 6, 5, 9, 4, 3, 1, ]
  exch( 9, 6)> [ , 11, 10, 8, 7, 6, 9, 5, 4, 3, 1, ]
  exch( 9, 7)> [ , 11, 10, 8, 7, 9, 6, 5, 4, 3, 1, ]
  exch( 9, 8)> [ , 11, 10, 8, 9, 7, 6, 5, 4, 3, 1, ]
+ 9          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, ]
  exch( 2, 1)> [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
- 1          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]
- 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, , ]
+ 2          : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]

Previous pageContentsNext page