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