CSC300 / CSC402: FixedPQSortedIncreasing [3/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[1]; 
    for (int j = 2; j <= N; j++)
      exch(j, j-1);
    a[N] = 0.0;
    N--;

    return result;
  }

Output

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

N=          128 Insert=  0.004 [Infinity] DelMin=  0.002 [Infinity]
N=          256 Insert=  0.003 [   0.750] DelMin=  0.002 [   1.000]
N=          512 Insert=  0.001 [   0.333] DelMin=  0.002 [   1.000]
N=        1,024 Insert=  0.008 [   8.000] DelMin=  0.017 [   8.500]
N=        2,048 Insert=  0.003 [   0.375] DelMin=  0.010 [   0.588]
N=        4,096 Insert=  0.008 [   2.667] DelMin=  0.043 [   4.300]
N=        8,192 Insert=  0.023 [   2.875] DelMin=  0.130 [   3.023]
N=       16,384 Insert=  0.144 [   6.261] DelMin=  0.276 [   2.123]
N=       32,768 Insert=  0.352 [   2.444] DelMin=  1.091 [   3.953]
N=       65,536 Insert=  1.024 [   2.909] DelMin=  4.582 [   4.200]
N=      131,072 Insert=  4.022 [   3.928] DelMin= 16.941 [   3.697]

Insert is linear, DeleteMin is linear

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

Previous pageContentsNext page