| CSC300 / CSC402: FixedPQSortedDecreasing [4/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[N]; a[N] = 0.0; N--; return result; } |
Output
[ , , , , , , , , , , , ] + 1 : [ , 1, , , , , , , , , , ] + 4 : [ , 4, 1, , , , , , , , , ] + 3 : [ , 4, 3, 1, , , , , , , , ] + 6 : [ , 6, 4, 3, 1, , , , , , , ] + 8 : [ , 8, 6, 4, 3, 1, , , , , , ] + 5 : [ , 8, 6, 5, 4, 3, 1, , , , , ] +11 : [ , 11, 8, 6, 5, 4, 3, 1, , , , ] +10 : [ , 11, 10, 8, 6, 5, 4, 3, 1, , , ] + 7 : [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, , ] + 9 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, ] + 2 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] - 1 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ] - 2 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, , ] + 2 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ] N= 128 Insert= 0.012 [Infinity] DelMin= 0.000 [ NaN] N= 256 Insert= 0.008 [ 0.667] DelMin= 0.000 [ NaN] N= 512 Insert= 0.003 [ 0.375] DelMin= 0.000 [ NaN] N= 1,024 Insert= 0.032 [ 10.667] DelMin= 0.001 [Infinity] N= 2,048 Insert= 0.007 [ 0.219] DelMin= 0.000 [ 0.000] N= 4,096 Insert= 0.015 [ 2.143] DelMin= 0.000 [ NaN] N= 8,192 Insert= 0.051 [ 3.400] DelMin= 0.000 [ NaN] N= 16,384 Insert= 0.138 [ 2.706] DelMin= 0.000 [ NaN] N= 32,768 Insert= 0.372 [ 2.696] DelMin= 0.000 [ NaN] N= 65,536 Insert= 1.359 [ 3.653] DelMin= 0.000 [ NaN] N= 131,072 Insert= 4.550 [ 3.348] DelMin= 0.000 [ NaN]
Insert is linear, DeleteMin is constant
[ , , , , , , , , , , , ] + 1 : [ , 1, , , , , , , , , , ] exch( 4, 1)> [ , 1, 4, , , , , , , , , ] + 4 : [ , 4, 1, , , , , , , , , ] exch( 3, 1)> [ , 4, 1, 3, , , , , , , , ] + 3 : [ , 4, 3, 1, , , , , , , , ] exch( 6, 1)> [ , 4, 3, 1, 6, , , , , , , ] exch( 6, 3)> [ , 4, 3, 6, 1, , , , , , , ] exch( 6, 4)> [ , 4, 6, 3, 1, , , , , , , ] + 6 : [ , 6, 4, 3, 1, , , , , , , ] exch( 8, 1)> [ , 6, 4, 3, 1, 8, , , , , , ] exch( 8, 3)> [ , 6, 4, 3, 8, 1, , , , , , ] exch( 8, 4)> [ , 6, 4, 8, 3, 1, , , , , , ] exch( 8, 6)> [ , 6, 8, 4, 3, 1, , , , , , ] + 8 : [ , 8, 6, 4, 3, 1, , , , , , ] exch( 5, 1)> [ , 8, 6, 4, 3, 1, 5, , , , , ] exch( 5, 3)> [ , 8, 6, 4, 3, 5, 1, , , , , ] exch( 5, 4)> [ , 8, 6, 4, 5, 3, 1, , , , , ] + 5 : [ , 8, 6, 5, 4, 3, 1, , , , , ] exch(11, 1)> [ , 8, 6, 5, 4, 3, 1, 11, , , , ] exch(11, 3)> [ , 8, 6, 5, 4, 3, 11, 1, , , , ] exch(11, 4)> [ , 8, 6, 5, 4, 11, 3, 1, , , , ] exch(11, 5)> [ , 8, 6, 5, 11, 4, 3, 1, , , , ] exch(11, 6)> [ , 8, 6, 11, 5, 4, 3, 1, , , , ] exch(11, 8)> [ , 8, 11, 6, 5, 4, 3, 1, , , , ] +11 : [ , 11, 8, 6, 5, 4, 3, 1, , , , ] exch(10, 1)> [ , 11, 8, 6, 5, 4, 3, 1, 10, , , ] exch(10, 3)> [ , 11, 8, 6, 5, 4, 3, 10, 1, , , ] exch(10, 4)> [ , 11, 8, 6, 5, 4, 10, 3, 1, , , ] exch(10, 5)> [ , 11, 8, 6, 5, 10, 4, 3, 1, , , ] exch(10, 6)> [ , 11, 8, 6, 10, 5, 4, 3, 1, , , ] exch(10, 8)> [ , 11, 8, 10, 6, 5, 4, 3, 1, , , ] +10 : [ , 11, 10, 8, 6, 5, 4, 3, 1, , , ] exch( 7, 1)> [ , 11, 10, 8, 6, 5, 4, 3, 1, 7, , ] exch( 7, 3)> [ , 11, 10, 8, 6, 5, 4, 3, 7, 1, , ] exch( 7, 4)> [ , 11, 10, 8, 6, 5, 4, 7, 3, 1, , ] exch( 7, 5)> [ , 11, 10, 8, 6, 5, 7, 4, 3, 1, , ] exch( 7, 6)> [ , 11, 10, 8, 6, 7, 5, 4, 3, 1, , ] + 7 : [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, , ] exch( 9, 1)> [ , 11, 10, 8, 7, 6, 5, 4, 3, 1, 9, ] exch( 9, 3)> [ , 11, 10, 8, 7, 6, 5, 4, 3, 9, 1, ] exch( 9, 4)> [ , 11, 10, 8, 7, 6, 5, 4, 9, 3, 1, ] exch( 9, 5)> [ , 11, 10, 8, 7, 6, 5, 9, 4, 3, 1, ] exch( 9, 6)> [ , 11, 10, 8, 7, 6, 9, 5, 4, 3, 1, ] exch( 9, 7)> [ , 11, 10, 8, 7, 9, 6, 5, 4, 3, 1, ] exch( 9, 8)> [ , 11, 10, 8, 9, 7, 6, 5, 4, 3, 1, ] + 9 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, ] exch( 2, 1)> [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 1, 2] + 2 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] - 1 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ] - 2 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, , ] + 2 : [ , 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, ]