-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTreeMinHeapUtilities.java
More file actions
187 lines (125 loc) · 4.6 KB
/
Copy pathTreeMinHeapUtilities.java
File metadata and controls
187 lines (125 loc) · 4.6 KB
1
2
3
4
5
6
7
8
9
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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
package cpsc331.assignment3;
import cpsc331.collections.MinHeap;
import java.util.NoSuchElementException;
import cpsc331.assignment3.TreeMinHeap;
//
// Provides utilities that can be used to test whether a given data structure
// is a TreeMinHeap
//
public class TreeMinHeapUtilities<T extends Comparable<T>> {
public boolean isTreeMinHeap(TreeMinHeap<T> H, int heapSize, boolean verbose) {
TreeMinHeap<T>.TreeNode root = H.getRoot();
TreeMinHeap<T>.TreeNode latest = H.getLatest();
if (root == null) {
if ((heapSize == 0) && (latest == null)) {
return true;
} else {
if ((heapSize != 0) && verbose) {
System.out.println("Root is null but heapSize is nonzero.");
};
if ((latest != null) && verbose) {
System.out.println("Root is null but latest is not null.");
};
return false;
}
} else {
boolean result = isSubHeap(root, 0, heapSize, verbose);
if (latest == null) {
if (verbose) {
System.out.println("Heap Size is positive but latest is null.");
};
result = false;
} else if (latest.getIndex() != heapSize - 1) {
if (verbose) {
System.out.println("INdex of latest is not heapSize-1");
};
result = false;
}
return result = true;
}
}
// Note: It is assumed that the node used as an input for the following
// method is always non-null. It is also assumed that the values stored
// at nodes are non-null.
public boolean isSubHeap(TreeMinHeap<T>.TreeNode node, int index,
int heapSize, boolean verbose) {
boolean result = true;
int thisIndex = node.getIndex();
if (thisIndex != index) {
if (verbose) {
System.out.print("Node whose expected index is ");
System.out.print(index);
System.out.print(" has index ");
System.out.print(thisIndex);
System.out.println(" instead.");
};
result = false;
};
T thisValue = node.getValue();
int leftIndex = 2 * index + 1;
TreeMinHeap<T>.TreeNode leftChild = node.getLeft();
if (leftIndex < heapSize) {
if (leftChild != null) {
T leftValue = leftChild.getValue();
if (leftValue.compareTo(thisValue) < 0) {
if (verbose) {
System.out.print("The value at the left child of the node with index ");
System.out.print(index);
System.out.println(" is less than the value at this node.");
};
result = false;
};
result = (result && isSubHeap(leftChild, leftIndex, heapSize, verbose));
} else {
if (verbose) {
System.out.print("The left child of the node with index ");
System.out.print(index);
System.out.println(" is missing.");
};
result = false;
}
} else {
if (leftChild != null) {
if (verbose) {
System.out.print("The node with index ");
System.out.print(index);
System.out.println(" has a left child when it should not.");
};
result = false;
}
};
int rightIndex = 2 * index + 2;
TreeMinHeap<T>.TreeNode rightChild = node.getRight();
if (rightIndex < heapSize) {
if (rightChild != null) {
T rightValue = rightChild.getValue();
if (rightValue.compareTo(thisValue) < 0) {
if (verbose) {
System.out.print("The value at the right child of the node with index ");
System.out.print(index);
System.out.println(" is less than the value at this node.");
};
result = false;
};
result = (result && isSubHeap(rightChild, rightIndex, heapSize, verbose));
} else {
if (verbose) {
System.out.print("The right chid of the node with index ");
System.out.print(index);
System.out.println(" is missing.");
};
result = false;
}
} else {
if (rightChild != null) {
if (verbose) {
System.out.print("The node with index ");
System.out.print(index);
System.out.println(" has a right child when it should not.");
};
result = false;
}
};
return result;
}
}