1package tests.persistent.queue;
2
3import ds.interfaces.PriorityQueue;
4
5import java.util.Random;
6
7import ds.persistent.queue.BinaryHeap;
8import ds.util.PV;
9import ds.util.P;
10
11import static ds.util.P.mkP;
12import static ds.util.V.mkV;
13import static ds.util.PV.mkPair;
14
15import tests.util.Args;
16
17public class BinaryHeapTrace {
18
19 public static void main(String [] args) {
20 int noOfElems = Args.getInt(args, 0, 1023);
21
22 (new Main(noOfElems)).run();
23 }
24
25 private static
26 class Main
27 extends tests.util.Main {
28 final int n;
29 final Random r;
30
31 BinaryHeap h;
32
33 Main(int n1) {
34 n = n1;
35 r = new Random();
36 h = BinaryHeap.empty();
37 }
38
39 void buildHeapRandom() {
40 startTime("building binary heap tree by inserting " +
41 n +
42 " random elements)");
43 for (int i = 0; i < n; ++i) {
44 int p = r.nextInt();
45 if ( n <= 100 )
46 msg("insert " + p + ", " + i);
47 h = h.insert(mkP(p), mkV(i));
48 }
49 stopTime();
50 }
51
52 void buildHeapAscending() {
53 startTime("building binary heap tree by inserting " +
54 n +
55 " ascending elements");
56 for (int i = 0; i < n; ++i) {
57 int p = i;
58 if ( n <= 100 )
59 msg("insert " + p + ", " + i);
60 h = h.insert(mkP(p), mkV(i));
61 }
62 stopTime();
63 }
64
65 void buildHeapDescending() {
66 startTime("building binary heap tree by inserting " +
67 n +
68 " descending elements");
69 for (int i = 0; i < n; ++i) {
70 int p = n - i - 1;
71 if ( n <= 100 )
72 msg("insert " + p + ", " + i);
73 h = h.insert(mkP(p), mkV(i));
74 }
75 stopTime();
76 }
77
78 void buildHeapConst() {
79 startTime("building binary heap tree by inserting " +
80 n +
81 " times the same element");
82 for (int i = 0; i < n; ++i) {
83 int p = 0;
84 if ( n <= 100 )
85 msg("insert " + p + ", " + i);
86 h = h.insert(mkP(p), mkV(i));
87 }
88 stopTime();
89 }
90
91 void deleteHeap() {
92 startTime("deleting a binary heap tree by removing " +
93 n +
94 " elements in ascending order");
95 for (int i = 0; i < n; ++i) {
96 PV pv = h.findMin();
97 if ( n <= 100 )
98 msg("remove " + pv.fst.prio + ", " + pv.snd.value);
99 h = h.removeMin();
100 }
101 msg("binary heap: h.isEmpty() == " + h.isEmpty());
102 stopTime();
103 }
104
105 void stats() {
106 msg("h.size() = " + h.size());
107 msg("h.depth() = " + h.depth());
108 msg("h.minDepth() = " + h.minDepth());
109 msg("h.inv() = " + h.inv());
110 msg("");
111 }
112
113 void memStats() {
114 msg(h.objStats());
115 }
116
117 void classStats() {
118 msg(BinaryHeap.stats());
119 }
120
121 public void run() {
122 nl();
123 buildHeapRandom();
124 stats();
125 memStats();
126 classStats();
127 deleteHeap();
128 stats();
129 classStats();
130
131 buildHeapAscending();
132 stats();
133 memStats();
134 classStats();
135 deleteHeap();
136 stats();
137 classStats();
138
139 buildHeapDescending();
140 stats();
141 memStats();
142 classStats();
143 deleteHeap();
144 stats();
145 classStats();
146
147 buildHeapConst();
148 stats();
149 memStats();
150 classStats();
151 deleteHeap();
152 stats();
153 classStats();
154 }
155 }
156}
Algorithmen & Datenstrukturen mit Java: tests.persistent.queue.BinaryHeapTrace
