| CSC300 / CSC402: FixedPQUnordered [5/7] | |
01 |
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, ]