CSC300 / CSC402: FixedPQHeap [6/7] Previous pageContentsNext page

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
  public void insert(double x) {        private void swim(int k) {                
    N++;                                  while (k > 1 && a[k/2] > a[k]) {        
    a[N] = x;                               int parent = k/2;                     
    swim(N);                                exch2(k, parent);                     
                                            k = parent;                           
  }                                     } }                                       
  public double delMin() {              private void sink(int k) {                
    double result = a[1];                 while (2*k <= N) {                      
                                            int child = 2*k;                      
    exch(1, N);                             if (2*k+1 < N && a[2*k] < a[2*k+1])  
    a[N] = 0.0;                               child = 2*k + 1;
    N--;                                    if (a[k] < a[child]) break;    
    sink(1);                                exch2(k, child);                                    
    return result;                          k = child;                                          
  }                                     } }                                                     

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, 2, 3, 6, 4, 5, 11, 10, 7, 9, 8]
- 1          : [ , 2, 4, 3, 6, 8, 5, 11, 10, 7, 9, ]
- 2          : [ , 3, 4, 5, 6, 8, 9, 11, 10, 7, , ]
+ 2          : [ , 2, 3, 5, 6, 4, 9, 11, 10, 7, 8, ]

N=          128 Insert=  0.002 [Infinity] DelMin=  0.000 [     NaN]
N=          256 Insert=  0.001 [   0.500] DelMin=  0.000 [     NaN]
N=          512 Insert=  0.001 [   1.000] DelMin=  0.000 [     NaN]
N=        1,024 Insert=  0.000 [   0.000] DelMin=  0.000 [     NaN]
N=        2,048 Insert=  0.000 [     NaN] DelMin=  0.001 [Infinity]
N=        4,096 Insert=  0.001 [Infinity] DelMin=  0.002 [   2.000]
N=        8,192 Insert=  0.001 [   1.000] DelMin=  0.002 [   1.000]
N=       16,384 Insert=  0.003 [   3.000] DelMin=  0.004 [   2.000]
N=       32,768 Insert=  0.004 [   1.333] DelMin=  0.005 [   1.250]
N=       65,536 Insert=  0.005 [   1.250] DelMin=  0.012 [   2.400]
N=      131,072 Insert=  0.014 [   2.800] DelMin=  0.029 [   2.417]
N=      262,144 Insert=  0.013 [   0.929] DelMin=  0.053 [   1.828]
N=      524,288 Insert=  0.025 [   1.923] DelMin=  0.114 [   2.151]
N=    1,048,576 Insert=  0.051 [   2.040] DelMin=  0.280 [   2.456]
N=    2,097,152 Insert=  0.113 [   2.216] DelMin=  0.571 [   2.039]
N=    4,194,304 Insert=  0.201 [   1.779] DelMin=  1.402 [   2.455]
N=    8,388,608 Insert=  0.402 [   2.000] DelMin=  3.600 [   2.568]
N=   16,777,216 Insert=  0.822 [   2.045] DelMin=  8.440 [   2.344]
N=   33,554,432 Insert=  1.619 [   1.970] DelMin= 21.522 [   2.550]

Insert is logarithmic, DeleteMin is logarithmic

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

Previous pageContentsNext page