Skip to content

Commit fbe348b

Browse files
govardhanshah456vil02
govardhanshah456
and
vil02
authored
* TheAlgorithms#4382 Bug Fix * TheAlgorithms#4382 Bug Fix * Made Requested Changes * Made Requested Changes * Made Requested Changes * Made Requested Changes * Made Requested Changes * Made Requested Changes * Made Requested Changes * Update src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> * Update src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com> --------- Co-authored-by: Piotr Idzik <65706193+vil02@users.noreply.github.com>
1 parent 906cd87 commit fbe348b

File tree

2 files changed

+181
-22
lines changed

2 files changed

+181
-22
lines changed

‎src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java

Lines changed: 20 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -8,46 +8,44 @@
88
*/
99
public class MedianOfRunningArray {
1010

11-
private PriorityQueue<Integer> p1;
12-
private PriorityQueue<Integer> p2;
11+
private PriorityQueue<Integer> maxHeap;
12+
private PriorityQueue<Integer> minHeap;
1313

1414
// Constructor
1515
public MedianOfRunningArray() {
16-
this.p1 = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap
17-
this.p2 = new PriorityQueue<>(); // Min Heap
16+
this.maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap
17+
this.minHeap = new PriorityQueue<>(); // Min Heap
1818
}
1919

2020
/*
2121
Inserting lower half of array to max Heap
2222
and upper half to min heap
2323
*/
2424
public void insert(Integer e) {
25-
p2.add(e);
26-
if (p2.size() - p1.size() > 1) {
27-
p1.add(p2.remove());
25+
if (!minHeap.isEmpty() && e < minHeap.peek()) {
26+
maxHeap.offer(e);
27+
if (maxHeap.size() > minHeap.size() + 1) {
28+
minHeap.offer(maxHeap.poll());
29+
}
30+
} else {
31+
minHeap.offer(e);
32+
if (minHeap.size() > maxHeap.size() + 1) {
33+
maxHeap.offer(minHeap.poll());
34+
}
2835
}
2936
}
3037

3138
/*
3239
Returns median at any given point
3340
*/
34-
public Integer median() {
35-
if (p1.size() == p2.size()) {
36-
return (p1.peek() + p2.peek()) / 2;
41+
public double median() {
42+
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
43+
throw new IllegalArgumentException("Enter at least 1 element, Median of empty list is not defined!");
3744
}
38-
return p1.size() > p2.size() ? p1.peek() : p2.peek();
39-
}
40-
41-
public static void main(String[] args) {
42-
/*
43-
Testing the median function
44-
*/
4545

46-
MedianOfRunningArray p = new MedianOfRunningArray();
47-
int[] arr = {10, 7, 4, 9, 2, 3, 11, 17, 14};
48-
for (int i = 0; i < 9; i++) {
49-
p.insert(arr[i]);
50-
System.out.print(p.median() + " ");
46+
if (maxHeap.size() == minHeap.size()) {
47+
return (maxHeap.peek() + minHeap.peek()) / 2.0;
5148
}
49+
return maxHeap.size() > minHeap.size() ? maxHeap.peek() * 1.0 : minHeap.peek() * 1.0;
5250
}
5351
}

‎src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java

Lines changed: 161 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,161 @@
1+
package com.thealgorithms.misc;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
import static org.junit.jupiter.api.Assertions.assertFalse;
5+
import static org.junit.jupiter.api.Assertions.assertThrows;
6+
7+
import org.apache.commons.lang3.tuple.Pair;
8+
import org.junit.jupiter.api.Test;
9+
10+
/**
11+
* Test case for Two sum Problem.
12+
* @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
13+
*/
14+
15+
public class MedianOfRunningArrayTest {
16+
private static final String EXCEPTION_MESSAGE = "Enter at least 1 element, Median of empty list is not defined!";
17+
18+
@Test
19+
public void testWhenInvalidInoutProvidedShouldThrowException() {
20+
MedianOfRunningArray stream = new MedianOfRunningArray();
21+
IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> stream.median());
22+
assertEquals(exception.getMessage(), EXCEPTION_MESSAGE);
23+
}
24+
25+
@Test
26+
public void testWithNegativeValues() {
27+
MedianOfRunningArray stream = new MedianOfRunningArray();
28+
stream.insert(-1);
29+
assertEquals(-1, stream.median());
30+
stream.insert(-2);
31+
assertEquals(-1.5, stream.median());
32+
stream.insert(-3);
33+
assertEquals(-2, stream.median());
34+
}
35+
36+
@Test
37+
public void testWithSingleValues() {
38+
MedianOfRunningArray stream = new MedianOfRunningArray();
39+
stream.insert(-1);
40+
assertEquals(-1, stream.median());
41+
}
42+
43+
@Test
44+
public void testWithRandomValues() {
45+
MedianOfRunningArray stream = new MedianOfRunningArray();
46+
stream.insert(10);
47+
assertEquals(10.0, stream.median());
48+
49+
stream.insert(5);
50+
assertEquals(7.5, stream.median());
51+
52+
stream.insert(20);
53+
assertEquals(10.0, stream.median());
54+
55+
stream.insert(15);
56+
assertEquals(12.5, stream.median());
57+
58+
stream.insert(25);
59+
assertEquals(15.0, stream.median());
60+
61+
stream.insert(30);
62+
assertEquals(17.5, stream.median());
63+
64+
stream.insert(35);
65+
assertEquals(20.0, stream.median());
66+
67+
stream.insert(1);
68+
assertEquals(17.5, stream.median());
69+
}
70+
71+
@Test
72+
public void testWithNegativeAndPositiveValues() {
73+
MedianOfRunningArray stream = new MedianOfRunningArray();
74+
stream.insert(-1);
75+
assertEquals(-1, stream.median());
76+
stream.insert(2);
77+
assertEquals(0.5, stream.median());
78+
stream.insert(-3);
79+
assertEquals(-1, stream.median());
80+
}
81+
82+
@Test
83+
public void testWithDuplicateValues() {
84+
MedianOfRunningArray stream = new MedianOfRunningArray();
85+
stream.insert(-1);
86+
assertEquals(-1, stream.median());
87+
stream.insert(-1);
88+
assertEquals(-1, stream.median());
89+
stream.insert(-1);
90+
assertEquals(-1, stream.median());
91+
}
92+
93+
@Test
94+
public void testWithDuplicateValuesB() {
95+
MedianOfRunningArray stream = new MedianOfRunningArray();
96+
stream.insert(10);
97+
stream.insert(20);
98+
stream.insert(10);
99+
stream.insert(10);
100+
stream.insert(20);
101+
stream.insert(0);
102+
stream.insert(50);
103+
assertEquals(10, stream.median());
104+
}
105+
106+
@Test
107+
public void testWithLargeValues() {
108+
MedianOfRunningArray stream = new MedianOfRunningArray();
109+
stream.insert(1000000);
110+
assertEquals(1000000, stream.median());
111+
stream.insert(12000);
112+
assertEquals(506000, stream.median());
113+
stream.insert(15000000);
114+
assertEquals(1000000, stream.median());
115+
stream.insert(2300000);
116+
assertEquals(1650000.00, stream.median());
117+
}
118+
119+
@Test
120+
public void testWithLargeCountOfValues() {
121+
MedianOfRunningArray stream = new MedianOfRunningArray();
122+
for (int i = 1; i <= 1000; i++) stream.insert(i);
123+
assertEquals(500.5, stream.median());
124+
}
125+
126+
@Test
127+
public void testWithThreeValuesInDescendingOrder() {
128+
MedianOfRunningArray stream = new MedianOfRunningArray();
129+
stream.insert(30);
130+
stream.insert(20);
131+
stream.insert(10);
132+
assertEquals(20.0, stream.median());
133+
}
134+
135+
@Test
136+
public void testWithThreeValuesInOrder() {
137+
MedianOfRunningArray stream = new MedianOfRunningArray();
138+
stream.insert(10);
139+
stream.insert(20);
140+
stream.insert(30);
141+
assertEquals(20.0, stream.median());
142+
}
143+
144+
@Test
145+
public void testWithThreeValuesNotInOrderA() {
146+
MedianOfRunningArray stream = new MedianOfRunningArray();
147+
stream.insert(30);
148+
stream.insert(10);
149+
stream.insert(20);
150+
assertEquals(20.0, stream.median());
151+
}
152+
153+
@Test
154+
public void testWithThreeValuesNotInOrderB() {
155+
MedianOfRunningArray stream = new MedianOfRunningArray();
156+
stream.insert(20);
157+
stream.insert(10);
158+
stream.insert(30);
159+
assertEquals(20.0, stream.median());
160+
}
161+
}

0 commit comments

Comments
 (0)