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