Skip to content

Commit dd715d4

Browse files
arash691arash691
authored
BAEL-4409 : codes have been added (eugenp#10925)
* BAEL-4409 : codes have been added * BAEL-4409 : how to implement min-max heap in java * BAEL-4409 : how to implement min-max heap in java
1 parent 51ceab1 commit dd715d4

2 files changed

Lines changed: 376 additions & 0 deletions

File tree

‎data-structures/src/main/java/com/baeldung/minmaxheap/MinMaxHeap.java‎

Lines changed: 344 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,344 @@
1+
package com.baeldung.minmaxheap;
2+
3+
import java.util.*;
4+
5+
/**
6+
* Created by arash on 15.06.21.
7+
*/
8+
9+
public class MinMaxHeap<T extends Comparable<T>> {
10+
private List<T> array;
11+
private int capacity;
12+
private int indicator;
13+
14+
MinMaxHeap(int capacity) {
15+
array = new ArrayList<>();
16+
this.capacity = capacity;
17+
indicator = 1;
18+
}
19+
20+
MinMaxHeap(List<T> array) {
21+
this.array = array;
22+
this.capacity = array.size();
23+
this.indicator = array.size() + 1;
24+
}
25+
26+
public List<T> getMinMaxHeap() {
27+
return array;
28+
}
29+
30+
public List<T> create() {
31+
for (int i = Math.floorDiv(array.size(), 2); i >= 1; i--) {
32+
pushDown(array, i);
33+
}
34+
return array;
35+
}
36+
37+
private void pushDown(List<T> array, int i) {
38+
if (isEvenLevel(i)) {
39+
pushDownMin(array, i);
40+
} else {
41+
pushDownMax(array, i);
42+
}
43+
}
44+
45+
private void pushDownMin(List<T> h, int i) {
46+
while (getLeftChildIndex(i) < indicator) {
47+
int indexOfSmallest = getIndexOfSmallestChildOrGrandChild(h, i);
48+
if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
49+
if (getParentIndex(getParentIndex(indexOfSmallest)) == i) {
50+
if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
51+
swap(indexOfSmallest - 1, i - 1, h);
52+
if (h.get(indexOfSmallest - 1).compareTo(h.get(getParentIndex(indexOfSmallest) - 1)) > 0) {
53+
swap(indexOfSmallest - 1, getParentIndex(indexOfSmallest) - 1, h);
54+
}
55+
}
56+
} else if (h.get(indexOfSmallest - 1).compareTo(h.get(i - 1)) < 0) {
57+
swap(indexOfSmallest - 1, i - 1, h);
58+
}
59+
} else {
60+
break;
61+
}
62+
i = indexOfSmallest;
63+
}
64+
}
65+
66+
private void pushDownMax(List<T> h, int i) {
67+
while (getLeftChildIndex(i) < indicator) {
68+
int indexOfGreatest = getIndexOfGreatestChildOrGrandChild(h, i);
69+
if (h.get(indexOfGreatest - 1).compareTo(h.get(i - 1)) > 0) {
70+
if (getParentIndex(getParentIndex(indexOfGreatest)) == i) {
71+
if (h.get(indexOfGreatest - 1).compareTo(h.get(i - 1)) > 0) {
72+
swap(indexOfGreatest - 1, i - 1, h);
73+
if (h.get(indexOfGreatest - 1).compareTo(h.get(getParentIndex(indexOfGreatest) - 1)) < 0) {
74+
swap(indexOfGreatest - 1, getParentIndex(indexOfGreatest) - 1, h);
75+
}
76+
}
77+
} else if (h.get(indexOfGreatest - 1).compareTo(h.get(i - 1)) > 0) {
78+
swap(indexOfGreatest - 1, i - 1, h);
79+
}
80+
} else {
81+
break;
82+
}
83+
i = indexOfGreatest;
84+
}
85+
}
86+
87+
private void swap(int i, int j, List<T> h) { //switch data at x with data at y
88+
T temp = h.get(i);
89+
h.set(i, h.get(j));
90+
h.set(j, temp);
91+
}
92+
93+
private int getLeftChildIndex(int i) {
94+
return 2 * i;
95+
}
96+
97+
private int getRightChildIndex(int i) {
98+
return ((2 * i) + 1);
99+
}
100+
101+
private int getParentIndex(int i) {
102+
return i / 2;
103+
}
104+
105+
private int getGrandparentIndex(int i) {
106+
return i / 4;
107+
}
108+
109+
private boolean isEvenLevel(int i) {
110+
return logBase2(i) % 2 == 0;
111+
}
112+
113+
private int logBase2(int num) {
114+
return (int) (Math.log(num) / Math.log(2));
115+
}
116+
117+
private int getMinChildIndex(int i) {
118+
return array.get(getLeftChildIndex(i)).compareTo(array.get(getRightChildIndex(i))) < 0 ? getLeftChildIndex(i) : getRightChildIndex(i);
119+
}
120+
121+
private int getMaxChildIndex(int i) {
122+
return array.get(getLeftChildIndex(i)).compareTo(array.get(getRightChildIndex(i))) > 0 ? getLeftChildIndex(i) : getRightChildIndex(i);
123+
}
124+
125+
private int getIndexOfSmallestChildOrGrandChild(List<T> h, int i) {
126+
int minIndex = getLeftChildIndex(i);
127+
T minValue = h.get(minIndex - 1);
128+
129+
if (getRightChildIndex(i) < indicator) {
130+
if (h.get(getRightChildIndex(i) - 1).compareTo(minValue) < 0) {
131+
minValue = h.get(getRightChildIndex(i));
132+
minIndex = getRightChildIndex(i);
133+
}
134+
} else {
135+
return minIndex;
136+
}
137+
138+
if (getLeftChildIndex(getLeftChildIndex(i)) < indicator) {
139+
if (h.get(getLeftChildIndex(getLeftChildIndex(i)) - 1).compareTo(minValue) < 0) {
140+
minValue = h.get(getLeftChildIndex(getLeftChildIndex(i)) - 1);
141+
minIndex = getLeftChildIndex(getLeftChildIndex(i));
142+
}
143+
} else {
144+
return minIndex; //if no leftmost grandchild
145+
}
146+
147+
if (getRightChildIndex(getLeftChildIndex(i)) < indicator) {
148+
if (h.get(getRightChildIndex(getLeftChildIndex(i)) - 1).compareTo(minValue) < 0) {
149+
minValue = h.get(getRightChildIndex(getLeftChildIndex(i)) - 1);
150+
minIndex = getRightChildIndex(getLeftChildIndex(i));
151+
}
152+
} else {
153+
return minIndex; //if no left-right grandchild
154+
}
155+
156+
if (getLeftChildIndex(getRightChildIndex(i)) < indicator) {
157+
if (h.get(getLeftChildIndex(getRightChildIndex(i)) - 1).compareTo(minValue) < 0) {
158+
minValue = h.get(getLeftChildIndex(getRightChildIndex(i)) - 1);
159+
minIndex = getLeftChildIndex(getRightChildIndex(i));
160+
}
161+
} else {
162+
return minIndex; //if no right-left grandchild
163+
}
164+
165+
if (getRightChildIndex(getRightChildIndex(i)) < indicator) {
166+
if (h.get(getRightChildIndex(getRightChildIndex(i)) - 1).compareTo(minValue) < 0) {
167+
minValue = h.get(getRightChildIndex(getRightChildIndex(i)) - 1);
168+
minIndex = getRightChildIndex(getRightChildIndex(i));
169+
}
170+
} else {
171+
return minIndex;
172+
}
173+
174+
return minIndex;
175+
}
176+
177+
private int getIndexOfGreatestChildOrGrandChild(List<T> h, int i) {
178+
int maxIndex = getLeftChildIndex(i); //we know left child exists
179+
T maxValue = h.get(maxIndex - 1);
180+
181+
if (getRightChildIndex(i) < indicator) {
182+
if (h.get(getRightChildIndex(i) - 1).compareTo(maxValue) > 0) {
183+
maxValue = h.get(getRightChildIndex(i) - 1);
184+
maxIndex = getRightChildIndex(i);
185+
}
186+
} else {
187+
return maxIndex;
188+
}
189+
190+
if (getLeftChildIndex(getLeftChildIndex(i)) < indicator) {
191+
if (h.get(getLeftChildIndex(getLeftChildIndex(i)) - 1).compareTo(maxValue) > 0) {
192+
maxValue = h.get(getLeftChildIndex(getLeftChildIndex(i)) - 1);
193+
maxIndex = getLeftChildIndex(getLeftChildIndex(i));
194+
}
195+
} else {
196+
return maxIndex; //if no leftmost grandchild
197+
}
198+
199+
if (getRightChildIndex(getLeftChildIndex(i)) < indicator) {
200+
if (h.get(getRightChildIndex(getLeftChildIndex(i)) - 1).compareTo(maxValue) > 0) {
201+
maxValue = h.get(getRightChildIndex(getLeftChildIndex(i)) - 1);
202+
maxIndex = getRightChildIndex(getLeftChildIndex(i));
203+
}
204+
} else {
205+
return maxIndex; //if no left-right grandchild
206+
}
207+
208+
if (getLeftChildIndex(getRightChildIndex(i)) < indicator) {
209+
if (h.get(getLeftChildIndex(getRightChildIndex(i)) - 1).compareTo(maxValue) > 0) {
210+
maxValue = h.get(getLeftChildIndex(getRightChildIndex(i)) - 1);
211+
maxIndex = getLeftChildIndex(getRightChildIndex(i));
212+
}
213+
} else {
214+
return maxIndex;
215+
}
216+
217+
if (getRightChildIndex(getRightChildIndex(i)) < indicator) {
218+
if (h.get(getRightChildIndex(getRightChildIndex(i)) - 1).compareTo(maxValue) > 0) {
219+
maxValue = h.get(getRightChildIndex(getRightChildIndex(i)) - 1);
220+
maxIndex = getRightChildIndex(getRightChildIndex(i));
221+
}
222+
} else {
223+
return maxIndex;
224+
}
225+
226+
return maxIndex;
227+
}
228+
229+
230+
public boolean isFull() {
231+
return indicator == this.capacity + 1;
232+
}
233+
234+
public boolean isEmpty() {
235+
return indicator == 1;
236+
}
237+
238+
public void insert(T item) {
239+
if (isEmpty()) {
240+
array.add(item);
241+
indicator++;
242+
} else if (!isFull()) {
243+
array.add(item);
244+
pushUp(array, indicator);
245+
indicator++;
246+
} else {
247+
throw new RuntimeException("invalid operation !!!");
248+
}
249+
}
250+
251+
private void pushUpMin(List<T> h, int i) {
252+
while (hasGrandparent(i) && h.get(i - 1).compareTo(h.get(getGrandparentIndex(i) - 1)) < 0) {
253+
swap(i - 1, getGrandparentIndex(i) - 1, h);
254+
i = getGrandparentIndex(i);
255+
}
256+
}
257+
258+
private void pushUpMax(List<T> h, int i) {
259+
while (hasGrandparent(i) && h.get(i - 1).compareTo(h.get(getGrandparentIndex(i) - 1)) > 0) {
260+
swap(i - 1, getGrandparentIndex(i) - 1, h);
261+
i = getGrandparentIndex(i);
262+
}
263+
}
264+
265+
private boolean hasGrandparent(int i) {
266+
return getParentIndex(i) > 1;
267+
}
268+
269+
private void pushUp(List<T> h, int i) {
270+
if (i != 1) {
271+
if (isEvenLevel(i)) {
272+
if (h.get(i - 1).compareTo(h.get(getParentIndex(i) - 1)) < 0) {
273+
pushUpMin(h, i);
274+
} else {
275+
swap(i - 1, getParentIndex(i) - 1, h);
276+
i = getParentIndex(i);
277+
pushUpMax(h, i);
278+
}
279+
} else if (h.get(i - 1).compareTo(h.get(getParentIndex(i) - 1)) > 0) {
280+
pushUpMax(h, i);
281+
} else {
282+
swap(i - 1, getParentIndex(i) - 1, h);
283+
i = getParentIndex(i);
284+
pushUpMin(h, i);
285+
}
286+
}
287+
}
288+
289+
public T min() {
290+
if (!isEmpty()) {
291+
return array.get(0);
292+
}
293+
return null;
294+
}
295+
296+
public T max() {
297+
if (!isEmpty()) {
298+
if (indicator == 2) {
299+
return array.get(0);
300+
}
301+
if (indicator == 3) {
302+
return array.get(1);
303+
}
304+
return array.get(1).compareTo(array.get(2)) < 0 ? array.get(2) : array.get(1);
305+
}
306+
return null;
307+
}
308+
309+
public T removeMin() {
310+
T min = min();
311+
if (min != null) {
312+
if (indicator == 2) {
313+
array.remove(indicator--);
314+
return min;
315+
}
316+
array.set(0, array.get(--indicator - 1));
317+
array.remove(indicator - 1);
318+
pushDown(array, 1);
319+
}
320+
return min;
321+
}
322+
323+
public T removeMax() {
324+
T max = max();
325+
if (max != null) {
326+
int maxIndex;
327+
if (indicator == 2) {
328+
maxIndex = 0;
329+
array.remove(--indicator - 1);
330+
return max;
331+
} else if (indicator == 3) {
332+
maxIndex = 1;
333+
array.remove(--indicator - 1);
334+
return max;
335+
} else {
336+
maxIndex = array.get(1).compareTo(array.get(2)) < 0 ? 2 : 1;
337+
}
338+
array.set(maxIndex, array.get(--indicator - 1));
339+
array.remove(indicator - 1);
340+
pushDown(array, maxIndex + 1);
341+
}
342+
return max;
343+
}
344+
}

‎data-structures/src/test/java/com/baeldung/minmaxheap/MinMaxHeapUnitTest.java‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.baeldung.minmaxheap;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
import java.util.Arrays;
6+
import java.util.List;
7+
8+
9+
public class MinMaxHeapUnitTest {
10+
11+
@Test
12+
public void givenUnOrderedArray_WhenCreateMinMaxHeap_ThenIsEqualWithMinMaxHeapOrdered() {
13+
List<Integer> list = Arrays.asList(34, 12, 28, 9, 30, 19, 1, 40);
14+
MinMaxHeap<Integer> minMaxHeap = new MinMaxHeap<>(list);
15+
minMaxHeap.create();
16+
Assert.assertEquals(Arrays.asList(1, 40, 34, 9, 30, 19, 28, 12), list);
17+
}
18+
19+
@Test
20+
public void givenNewElement_WhenInserted_ThenIsEqualWithMinMaxHeapOrdered() {
21+
MinMaxHeap<Integer> minMaxHeap = new MinMaxHeap(8);
22+
minMaxHeap.insert(34);
23+
minMaxHeap.insert(12);
24+
minMaxHeap.insert(28);
25+
minMaxHeap.insert(9);
26+
minMaxHeap.insert(30);
27+
minMaxHeap.insert(19);
28+
minMaxHeap.insert(1);
29+
minMaxHeap.insert(40);
30+
Assert.assertEquals(Arrays.asList(1, 40, 28, 12, 30, 19, 9, 34), minMaxHeap.getMinMaxHeap());
31+
}
32+
}

0 commit comments

Comments
 (0)