CSC300 / CSC402: FixedPQUnordered [5/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;


  }
  public double delMin() {              private int minPosition() {                          
    int m = minPosition();                int result = 1;                              
    double result = a[m];                 for (int i=2; i<=N; i++)                     
    exch(m, N);                             if (a[i] < a[result]) result = i;    
    a[N] = 0.0;                           return result;                               
    N--;                                }

    return result;
  }

Output

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

N=          128 Insert=  0.002 [Infinity] DelMin=  0.001 [Infinity]
N=          256 Insert=  0.000 [   0.000] DelMin=  0.001 [   1.000]
N=          512 Insert=  0.001 [Infinity] DelMin=  0.002 [   2.000]
N=        1,024 Insert=  0.000 [   0.000] DelMin=  0.005 [   2.500]
N=        2,048 Insert=  0.000 [     NaN] DelMin=  0.005 [   1.000]
N=        4,096 Insert=  0.001 [Infinity] DelMin=  0.010 [   2.000]
N=        8,192 Insert=  0.001 [   1.000] DelMin=  0.043 [   4.300]
N=       16,384 Insert=  0.002 [   2.000] DelMin=  0.109 [   2.535]
N=       32,768 Insert=  0.002 [   1.000] DelMin=  0.430 [   3.945]
N=       65,536 Insert=  0.002 [   1.000] DelMin=  2.089 [   4.858]
N=      131,072 Insert=  0.004 [   2.000] DelMin=  8.483 [   4.061]

Insert is constant, DeleteMin is linear

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

Previous pageContentsNext page