Skip to content

Commit 24dce2a

Browse files
benaichbenaich
committed
Update heap
1 parent fd1057a commit 24dce2a

File tree

3 files changed

+104
-72
lines changed

3 files changed

+104
-72
lines changed

‎Heap/HeapModule.java‎

Lines changed: 33 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -3,15 +3,14 @@
33
public class HeapModule {
44

55
public static interface Heap<T> {
6-
76
Heap left();
87
Heap right();
98
T data();
109
int rank();
1110
boolean isEmpty();
11+
int size();
1212
@Override
1313
String toString();
14-
int size();
1514
}
1615

1716
public static class NonEmptyHeap<T> implements Heap<T> {
@@ -32,76 +31,94 @@ public NonEmptyHeap(int r, T x, Heap a, Heap b) {
3231
right = b;
3332
}
3433

34+
@Override
3535
public Heap left() {
3636
return left;
3737
}
3838

39+
@Override
3940
public Heap right() {
4041
return right;
4142
}
4243

44+
@Override
4345
public T data() {
4446
return data;
4547
}
4648

49+
@Override
4750
public int rank() {
4851
return rank;
4952
}
5053

54+
@Override
5155
public boolean isEmpty() {
5256
return false;
5357
}
5458

59+
@Override
5560
public int size(){
5661
return 1 + left.size() + right.size();
5762
}
5863
}
5964

6065
public static final Heap<? extends Object> EMPTY = new Heap<Object>() {
6166

67+
@Override
6268
public Heap left() {
6369
throw new UnsupportedOperationException();
6470
}
6571

72+
@Override
6673
public Heap right() {
6774
throw new UnsupportedOperationException();
6875
}
6976

77+
@Override
7078
public Object data() {
7179
throw new UnsupportedOperationException();
7280
}
7381

82+
@Override
7483
public int rank() {
7584
return 0;
7685
}
7786

87+
@Override
7888
public String toString() {
7989
return "";
8090
}
8191

92+
@Override
8293
public boolean isEmpty() {
8394
return true;
8495
}
96+
97+
@Override
8598
public int size(){
8699
return 0;
87100
}
88101
};
89102

103+
/* retourn EMPTY instnace (singleton pattern) */
90104
public static <T> Heap<T> emptyHeap() {
91105
return (Heap) EMPTY;
92106
}
93-
107+
108+
/* build a heap v1 */
94109
public static <T extends Comparable<? super T>> Heap<T> heap(T x, Heap<T> a, Heap<T> b) {
95110
if (a.rank() > b.rank()) {
96111
return new NonEmptyHeap<>(b.rank() + 1, x, a, b);
97112
}
98113
return new NonEmptyHeap<>(a.rank() + 1, x, b, a);
99114
}
100115

116+
/* build a heap v2 */
101117
public static <T extends Comparable<? super T>> Heap<T> heap(T x) {
102118
return heap(x, emptyHeap(), emptyHeap());
103119
}
104120

121+
/* insert an element into a heap */
105122
public static <T extends Comparable<? super T>> Heap<T> insert(Heap<T> a, T x) {
106123
if (a.isEmpty()) {
107124
return heap(x);
@@ -112,38 +129,18 @@ public static <T extends Comparable<? super T>> Heap<T> insert(Heap<T> a, T x) {
112129
return heap(x, a.left(), insert(a.right(), a.data()));
113130
}
114131
}
115-
132+
133+
/* create a balanced heap from an array */
116134
public static <T extends Comparable<? super T>> Heap<T> insert(T... array) {
117135
Heap<T> root = emptyHeap();
118136
for (T item : array) {
119137
root = insert(root, item);
120138
}
121139
return root;
122140
}
123-
124-
public static <T extends Comparable<? super T>> Heap<T> leftList(T... array) {
125-
Heap<T> root = emptyHeap();
126-
for (T item : array) {
127-
root = merge(root, heap(item));
128-
}
129-
return root;
130-
}
131-
132-
public static <T extends Comparable<? super T>> Heap<T> merge(Heap<T> a, Heap<T> b) {
133-
if (a.isEmpty()) {
134-
return b;
135-
}
136-
if (b.isEmpty()) {
137-
return a;
138-
}
139-
140-
if (a.data().compareTo(b.data()) <= 0) {
141-
return heap(a.data(), a.left(), merge(a.right(), b));
142-
}
143-
return heap(b.data(), b.left(), merge(a, b.right()));
144-
}
145141

146-
public static <T extends Comparable<? super T>> Heap<T> simpleMerge(Heap<T> a, Heap<T> b) {
142+
/* merge two balanced heaps into one balanced heap*/
143+
public static <T extends Comparable<? super T>> Heap<T> merge(Heap<T> a, Heap<T> b) {
147144
if (a.isEmpty()) {
148145
return b;
149146
}
@@ -157,6 +154,7 @@ public static <T extends Comparable<? super T>> Heap<T> simpleMerge(Heap<T> a, H
157154
return heap(b.data(), merge(a.data(), b.left(), b.right()), merge(a.left(), a.right()));
158155
}
159156

157+
/* merge a key + two balanced heaps into one balanced heap*/
160158
public static <T extends Comparable<? super T>> Heap<T> merge(T x, Heap<T> a, Heap<T> b) {
161159
if (a.isEmpty()) {
162160
return insert(a, x);
@@ -168,26 +166,29 @@ public static <T extends Comparable<? super T>> Heap<T> merge(T x, Heap<T> a, He
168166
if ((x.compareTo(a.data()) <= 0) && (x.compareTo(b.data()) <= 0)) {
169167
return heap(x, a, b);
170168
}
171-
if ((a.data().compareTo(b.data()) <= 0) && (a.data().compareTo(x) <= 0)) {
169+
if (a.data().compareTo(b.data()) <= 0) {
172170
return heap(a.data(), merge(x, a.left(), a.right()), b);
173171
}
174172
return heap(b.data(), merge(x, b.left(), b.right()), a);
175173
}
176174

175+
/* return the minimum key of a heap */
177176
public static <T extends Comparable<? super T>> T min(Heap<T> root) {
178177
if (root == null) {
179178
return null;
180179
}
181180
return root.data();
182181
}
183182

183+
/* remove the minimum key of a heap */
184184
public static <T extends Comparable<? super T>> Heap<T> delete(Heap<T> root) {
185185
if (root == null) {
186186
return null;
187187
}
188188
return merge(root.left(), root.right());
189189
}
190190

191+
/* print heap element */
191192
public static <T> void printNice(Heap<T> root, int level) {
192193
if (root.isEmpty()) {
193194
return;
@@ -207,14 +208,12 @@ public static <T> void printNice(Heap<T> root, int level) {
207208
public static void main(String[] args) {
208209

209210
Heap<Integer> heap1 = insert(5, 9, 3);
210-
System.out.println("------------ Balanced Heap ------------");
211+
System.out.println("------------ Balanced Heap 1 ------------");
211212
printNice(heap1, 1);
212213
Heap<Integer> heap3 = insert(1, 8, 2);
213-
System.out.println("------------ Balanced Heap ------------");
214+
System.out.println("------------ Balanced Heap 2 ------------");
214215
printNice(heap3, 1);
215-
printNice(simpleMerge(heap1, heap3), 1);
216-
Heap<Integer> heap2 = leftList(5, 9, 3, 1, 2, 15, 22);
217-
System.out.println("------------ LeftList Heap ------------");
218-
printNice(heap2, 1);
216+
System.out.println("------------ Merge Heap 1 & Heap 2 ------------");
217+
printNice(merge(heap1, heap3), 1);
219218
}
220219
}

‎Heap/LeftistModule.java‎

Lines changed: 38 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -53,26 +53,32 @@ public NonEmptyLeftist(int r, T x, Leftist a, Leftist b) {
5353
right = b;
5454
}
5555

56+
@Override
5657
public Leftist left() {
5758
return left;
5859
}
5960

61+
@Override
6062
public Leftist right() {
6163
return right;
6264
}
6365

66+
@Override
6467
public T data() {
6568
return data;
6669
}
6770

71+
@Override
6872
public int rank() {
6973
return rank;
7074
}
7175

76+
@Override
7277
public boolean isEmpty() {
7378
return false;
7479
}
7580

81+
@Override
7682
public int size() {
7783
return 1 + left.size() + right.size();
7884
}
@@ -101,30 +107,37 @@ public static class Empty<T extends Comparable<? super T>> implements Leftist<T>
101107

102108
static protected final Empty empty = new Empty();
103109

110+
@Override
104111
public Leftist left() {
105112
throw new UnsupportedOperationException();
106113
}
107114

115+
@Override
108116
public Leftist right() {
109117
throw new UnsupportedOperationException();
110118
}
111119

120+
@Override
112121
public T data() {
113122
throw new UnsupportedOperationException();
114123
}
115124

125+
@Override
116126
public int rank() {
117127
return 0;
118128
}
119129

130+
@Override
120131
public String toString() {
121132
return "";
122133
}
123134

135+
@Override
124136
public boolean isEmpty() {
125137
return true;
126138
}
127139

140+
@Override
128141
public int size() {
129142
return 0;
130143
}
@@ -143,25 +156,30 @@ public Leftist<T> delete() {
143156
}
144157
};
145158

159+
/* retourn EMPTY instnace (singleton pattern) */
146160
public static <T extends Comparable<? super T>> Leftist<T> emptyLeftist() {
147161
return (Leftist) Empty.empty;
148162
}
149163

164+
/* build a leftist heap v1 */
150165
public static <T extends Comparable<? super T>> Leftist<T> heap(T x, Leftist<T> a, Leftist<T> b) {
151166
if (a.rank() > b.rank()) {
152167
return new NonEmptyLeftist<>(b.rank() + 1, x, a, b);
153168
}
154169
return new NonEmptyLeftist<>(a.rank() + 1, x, b, a);
155170
}
156171

172+
/* build a leftist heap v2 */
157173
public static <T extends Comparable<? super T>> Leftist<T> heap(T x) {
158174
return heap(x, emptyLeftist(), emptyLeftist());
159175
}
160-
176+
177+
/* used by HuffmanFunctionalProgramming package */
161178
public static <T extends Comparable<? super T>> Leftist<T> insert(Leftist<T> p, T val) {
162179
return p.insert(val);
163180
}
164181

182+
/* print heap element */
165183
public static <T extends Comparable<? super T>> void printNice(Leftist<T> root, int level) {
166184
if (root.isEmpty()) {
167185
return;
@@ -180,12 +198,24 @@ public static <T extends Comparable<? super T>> void printNice(Leftist<T> root,
180198

181199
public static void main(String[] args) {
182200

183-
Leftist<Integer> p = emptyLeftist();
184-
p = p.insert(2, 3, 4, 1, 2);
185-
// p = insert(emptyLeftist(), 2);
186-
printNice(p, 1);
187-
System.out.println("-------------");
188-
p = p.delete();
189-
printNice(p, 1);
201+
Leftist<Integer> p1 = emptyLeftist();
202+
Leftist<Integer> p2 = emptyLeftist();
203+
204+
p1 = p1.insert(2, 3, 4, 1, 2);
205+
System.out.println("----------- Leftits Heap 1 -----------");
206+
printNice(p1, 1);
207+
System.out.println("----------- delete -----------");
208+
p1 = p1.delete();
209+
printNice(p1, 1);
210+
211+
p2 = p2.insert(5, 9, 3, 1, 2, 15, 22);
212+
System.out.println("----------- Leftits Heap 1 -----------");
213+
printNice(p2, 1);
214+
215+
Leftist<Integer> p3 = p1.merge(p2);
216+
System.out.println("----------- merge Heap 1 & Heap 2 -----------");
217+
printNice(p3, 1);
218+
219+
190220
}
191221
}

0 commit comments

Comments
 (0)