CSC300: Priority Queues, Heaps, and Heapsort
(Click here for one slide per page)
In three parts
In these videos I will use some notes from the textbook:
|
01
02
03
04
05
06
07
08
09
10
11
12
|
package algs24;
// This is a toy interface for Priority Queues
// You are not allowed to insert 0.0
public interface PQ {
public int size();
public boolean isEmpty();
public void insert(double x);
public double min();
public double delMin();
public void toGraphviz();
}
|
|
|
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
package algs24;
import java.util.Scanner;
import stdlib.*;
public class TestPQ {
public static enum Order { INCREASING, DECREASING, RANDOM }
public static void main(String[] args) {
show(11, true, "1 4 3 6 8 5 11 10 7 9 2 - - 2"); // Example from text
show(9, true, "1 2 3 4 5 6 7 8 9 - - - - - - - -");
show(9, true, "9 8 7 6 5 4 3 2 1 - - - - - - - -");
showRandom(10, true);
double prevInsert = 0;
double prevDelMin = 0;
for (int N = 128; N<=MAX; N += N) {
timeTrial(N, Order.RANDOM);
StdOut.format("N=%,13d Insert=%7.3f [%8.3f] DelMin=%7.3f [%8.3f]\n", N, timeInsert, timeInsert/prevInsert, timeDelMin, timeDelMin/prevDelMin);
prevInsert = timeInsert;
prevDelMin = timeDelMin;
}
}
private static int MAX=200_000;
private static PQ getPQ (int N) {
//return new FixedPQSortedIncreasing(N);
//return new FixedPQSortedDecreasing(N);
//return new FixedPQUnordered(N);
MAX=50_000_000; return new FixedPQHeap(N);
}
private static double timeInsert;
private static double timeDelMin;
private static void timeTrial(int N, Order order) {
SHOW_STEPS=false;
PQ pqTime = getPQ(N);
Stopwatch sw1 = new Stopwatch();
for (int i=0; i<N; i+=1) {
double item = StdRandom.uniform(1,N+1);
switch (order) {
case INCREASING: pqTime.insert (i); break;
case DECREASING: pqTime.insert(N-i); break;
case RANDOM: pqTime.insert (item); break;
}
}
timeInsert = sw1.elapsedTime();
Stopwatch sw2 = new Stopwatch();
for (int i=0; i<N; i+= 1) {
pqTime.delMin();
}
timeDelMin = sw2.elapsedTime();
}
public static boolean SHOW_STEPS=false;
private static void showRandom (int N, boolean showSteps) {
SHOW_STEPS=showSteps;
PQ pq = getPQ(N);
pq.toGraphviz();
StdOut.format(" %s\n", pq);
for (int i=0; i<4*N; i+=1) {
if (pq.size() > N/2 && (pq.size() == N || StdRandom.random()<.45)) {
double item = pq.delMin();
StdOut.format("-%2.0f : %s\n", item, pq);
} else {
double item = StdRandom.uniform(10,100);
pq.insert(item);
StdOut.format("+%2.0f : %s\n", item, pq);
}
}
StdOut.println();
}
private static void show (int N, boolean showSteps, String input) {
SHOW_STEPS=showSteps;
Scanner s = new Scanner(input);
PQ pq = getPQ(N);
pq.toGraphviz();
StdOut.format(" %s\n", pq);
while (s.hasNext()) {
String next = s.next();
if ("-".equals(next)) {
double item = pq.delMin();
StdOut.format("-%2.0f : %s\n", item, pq);
} else {
double item = Integer.parseInt(next);
pq.insert(item);
StdOut.format("+%2.0f : %s\n", item, pq);
}
pq.toGraphviz();
}
StdOut.println();
s.close();
}
}
|
|
|
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
package algs24;
import stdlib.*;
import java.util.Arrays;
public class FixedPQSortedIncreasing implements PQ {
private int N;
private double[] a;
public FixedPQSortedIncreasing(int capacity){ N = 0; a = new double[capacity+1]; }
public void toGraphviz() { }
public String toString () { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
public int size() { return N; }
public boolean isEmpty() { return N == 0; }
public void insert(double x) {
if (x == 0) throw new Error ("No zeroes allowed");
if (N >= a.length-1) throw new Error("Overflow");
N++;
a[N] = x;
for (int j = N; j > 1 && a[j] < a[j-1]; j--)
exch2(j, j-1);
}
public double min() {
return a[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;
}
private void exch(int i, int j) {
double oldi = a[i];
double oldj = a[j];
a[i] = oldj;
a[j] = oldi;
if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
}
private void exch2(int i, int j) {
double oldi = a[i];
double oldj = a[j];
if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
a[i] = oldj;
a[j] = oldi;
}
private boolean isSorted() {
for (int i = 2; i < N; i++)
if (a[i] < a[i-1]) return false;
return true;
}
}
|
|
|
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
package algs24;
import stdlib.*;
import java.util.Arrays;
public class FixedPQSortedDecreasing implements PQ {
private int N;
private double[] a;
public FixedPQSortedDecreasing(int capacity){ N = 0; a = new double[capacity+1]; }
public void toGraphviz() { }
public String toString () { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
public int size() { return N; }
public boolean isEmpty() { return N == 0; }
public void insert(double x) {
if (x == 0) throw new Error ("No zeroes allowed");
if (N >= a.length-1) throw new Error("Overflow");
N++;
a[N] = x;
for (int j = N; j > 1 && a[j] > a[j-1]; j--)
exch2(j, j-1);
}
public double min() {
return a[N];
}
public double delMin() {
double result = a[N];
a[N] = 0.0;
N--;
return result;
}
private void exch2(int i, int j) {
double oldi = a[i];
double oldj = a[j];
if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
a[i] = oldj;
a[j] = oldi;
}
}
|
|
|
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
package algs24;
import stdlib.*;
import java.util.Arrays;
public class FixedPQUnordered implements PQ {
private int N;
private double[] a;
public FixedPQUnordered(int capacity) { N = 0; a = new double[capacity+1]; }
public void toGraphviz() { }
public String toString () { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
public int size() { return N; }
public boolean isEmpty() { return N == 0; }
public void insert(double x) {
if (x == 0) throw new Error ("No zeroes allowed");
if (N >= a.length-1) throw new Error("Overflow");
N++;
a[N] = x;
}
private int minPosition() {
if (N<=0) throw new Error("Underflow");
int result = 1;
for (int i=2; i<=N; i++)
if (a[i] < a[result]) result = i;
return result;
}
public double min() {
int m = minPosition();
return a[m];
}
public double delMin() {
int m = minPosition();
double result = a[m];
exch2(m, N);
a[N] = 0.0;
N--;
return result;
}
private void exch2(int i, int j) {
double oldi = a[i];
double oldj = a[j];
if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
a[i] = oldj;
a[j] = oldi;
}
}
|
|
|
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
package algs24;
import stdlib.*;
import java.util.Arrays;
public class FixedPQHeap implements PQ {
private int N;
private double[] a;
public FixedPQHeap(int capacity) { N = 0; a = new double[capacity+1]; }
public void toGraphviz() { GraphvizBuilder.binaryHeapToFile (a, N); }
public String toString () { return Arrays.toString(a).replaceAll(" 0\\.0", " ").replaceAll("\\[0\\.0", "[ ").replaceAll("\\.0", ""); }
public int size() { return N; }
public boolean isEmpty() { return N == 0; }
public void insert(double x) {
if (x == 0) throw new Error ("No zeroes allowed");
if (N >= a.length-1) throw new Error("Overflow");
N++;
a[N] = x;
swim(N);
}
public double min() {
if (N <= 0) throw new Error("Underflow");
return a[1];
}
public double delMin() {
double result = min();
exch(1, N);
a[N] = 0.0;
N--;
sink(1);
return result;
}
private boolean isMinHeap() {
for (int i = 2; i < N; i++)
if (a[i] < a[i/2]) return false;
return true;
}
// for comparison:
private boolean isSorted() {
for (int i = 2; i < N; i++)
if (a[i] < a[i-1]) return false;
return true;
}
private void swim(int k) {
while (k > 1 && a[k/2] > a[k]) {
int parent = k/2;
exch2(k, parent);
k = parent;
}
}
private void sink(int k) {
while (2*k <= N) {
int left = 2*k;
int right = 2*k + 1;
int child;
if (right > N || a[left] < a[right])
child = left;
else
child = right;
if (a[k] <= a[child]) break;
exch2(k, child);
k = child;
}
}
private void exch(int i, int j) {
double oldi = a[i];
double oldj = a[j];
a[i] = oldj;
a[j] = oldi;
if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
}
private void exch2(int i, int j) {
double oldi = a[i];
double oldj = a[j];
if (TestPQ.SHOW_STEPS) { StdOut.format(" exch(%2.0f,%2.0f)> %s\n", oldi, oldj, this); toGraphviz(); }
a[i] = oldj;
a[j] = oldi;
}
}
|
|
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
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, ]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
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, ]
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
|
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, ]
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 < 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, ]
Revised: 2008/03/17 13:01