Skip to content

Commit 2f5bc8c

Browse files
alxkmalxkm
authored
refactor: improve median calculator class design and readability (#6349)
1 parent 8512f12 commit 2f5bc8c

File tree

2 files changed

+93
-69
lines changed

2 files changed

+93
-69
lines changed

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

Lines changed: 53 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -4,50 +4,74 @@
44
import java.util.PriorityQueue;
55

66
/**
7-
* @author shrutisheoran
7+
* A generic abstract class to compute the median of a dynamically growing stream of numbers.
8+
*
9+
* @param <T> the number type, must extend Number and be Comparable
10+
*
11+
* Usage:
12+
* Extend this class and implement {@code calculateAverage(T a, T b)} to define how averaging is done.
813
*/
914
public abstract class MedianOfRunningArray<T extends Number & Comparable<T>> {
1015

11-
private PriorityQueue<T> maxHeap;
12-
private PriorityQueue<T> minHeap;
16+
private final PriorityQueue<T> maxHeap; // Lower half (max-heap)
17+
private final PriorityQueue<T> minHeap; // Upper half (min-heap)
1318

14-
// Constructor
1519
public MedianOfRunningArray() {
16-
this.maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap
17-
this.minHeap = new PriorityQueue<>(); // Min Heap
20+
this.maxHeap = new PriorityQueue<>(Collections.reverseOrder());
21+
this.minHeap = new PriorityQueue<>();
1822
}
1923

20-
/*
21-
Inserting lower half of array to max Heap
22-
and upper half to min heap
24+
/**
25+
* Inserts a new number into the data structure.
26+
*
27+
* @param element the number to insert
2328
*/
24-
public void insert(final T e) {
25-
if (!minHeap.isEmpty() && e.compareTo(minHeap.peek()) < 0) {
26-
maxHeap.offer(e);
27-
if (maxHeap.size() > minHeap.size() + 1) {
28-
minHeap.offer(maxHeap.poll());
29-
}
29+
public final void insert(final T element) {
30+
if (!minHeap.isEmpty() && element.compareTo(minHeap.peek()) < 0) {
31+
maxHeap.offer(element);
32+
balanceHeapsIfNeeded();
3033
} else {
31-
minHeap.offer(e);
32-
if (minHeap.size() > maxHeap.size() + 1) {
33-
maxHeap.offer(minHeap.poll());
34-
}
34+
minHeap.offer(element);
35+
balanceHeapsIfNeeded();
3536
}
3637
}
3738

38-
/*
39-
Returns median at any given point
39+
/**
40+
* Returns the median of the current elements.
41+
*
42+
* @return the median value
43+
* @throws IllegalArgumentException if no elements have been inserted
4044
*/
41-
public T median() {
45+
public final T getMedian() {
4246
if (maxHeap.isEmpty() && minHeap.isEmpty()) {
43-
throw new IllegalArgumentException("Enter at least 1 element, Median of empty list is not defined!");
44-
} else if (maxHeap.size() == minHeap.size()) {
45-
T maxHeapTop = maxHeap.peek();
46-
T minHeapTop = minHeap.peek();
47-
return calculateAverage(maxHeapTop, minHeapTop);
47+
throw new IllegalArgumentException("Median is undefined for an empty data set.");
4848
}
49-
return maxHeap.size() > minHeap.size() ? maxHeap.peek() : minHeap.peek();
49+
50+
if (maxHeap.size() == minHeap.size()) {
51+
return calculateAverage(maxHeap.peek(), minHeap.peek());
52+
}
53+
54+
return (maxHeap.size() > minHeap.size()) ? maxHeap.peek() : minHeap.peek();
5055
}
5156

52-
public abstract T calculateAverage(T a, T b);
57+
/**
58+
* Calculates the average between two values.
59+
* Concrete subclasses must define how averaging works (e.g., for Integer, Double, etc.).
60+
*
61+
* @param a first number
62+
* @param b second number
63+
* @return the average of a and b
64+
*/
65+
protected abstract T calculateAverage(T a, T b);
66+
67+
/**
68+
* Balances the two heaps so that their sizes differ by at most 1.
69+
*/
70+
private void balanceHeapsIfNeeded() {
71+
if (maxHeap.size() > minHeap.size() + 1) {
72+
minHeap.offer(maxHeap.poll());
73+
} else if (minHeap.size() > maxHeap.size() + 1) {
74+
maxHeap.offer(minHeap.poll());
75+
}
76+
}
5377
}

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

Lines changed: 40 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -11,81 +11,81 @@
1111
*/
1212

1313
public class MedianOfRunningArrayTest {
14-
private static final String EXCEPTION_MESSAGE = "Enter at least 1 element, Median of empty list is not defined!";
14+
private static final String EXCEPTION_MESSAGE = "Median is undefined for an empty data set.";
1515

1616
@Test
1717
public void testWhenInvalidInoutProvidedShouldThrowException() {
1818
var stream = new MedianOfRunningArrayInteger();
19-
IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> stream.median());
19+
IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, stream::getMedian);
2020
assertEquals(exception.getMessage(), EXCEPTION_MESSAGE);
2121
}
2222

2323
@Test
2424
public void testWithNegativeValues() {
2525
var stream = new MedianOfRunningArrayInteger();
2626
stream.insert(-1);
27-
assertEquals(-1, stream.median());
27+
assertEquals(-1, stream.getMedian());
2828
stream.insert(-2);
29-
assertEquals(-1, stream.median());
29+
assertEquals(-1, stream.getMedian());
3030
stream.insert(-3);
31-
assertEquals(-2, stream.median());
31+
assertEquals(-2, stream.getMedian());
3232
}
3333

3434
@Test
3535
public void testWithSingleValues() {
3636
var stream = new MedianOfRunningArrayInteger();
3737
stream.insert(-1);
38-
assertEquals(-1, stream.median());
38+
assertEquals(-1, stream.getMedian());
3939
}
4040

4141
@Test
4242
public void testWithRandomValues() {
4343
var stream = new MedianOfRunningArrayInteger();
4444
stream.insert(10);
45-
assertEquals(10, stream.median());
45+
assertEquals(10, stream.getMedian());
4646

4747
stream.insert(5);
48-
assertEquals(7, stream.median());
48+
assertEquals(7, stream.getMedian());
4949

5050
stream.insert(20);
51-
assertEquals(10, stream.median());
51+
assertEquals(10, stream.getMedian());
5252

5353
stream.insert(15);
54-
assertEquals(12, stream.median());
54+
assertEquals(12, stream.getMedian());
5555

5656
stream.insert(25);
57-
assertEquals(15, stream.median());
57+
assertEquals(15, stream.getMedian());
5858

5959
stream.insert(30);
60-
assertEquals(17, stream.median());
60+
assertEquals(17, stream.getMedian());
6161

6262
stream.insert(35);
63-
assertEquals(20, stream.median());
63+
assertEquals(20, stream.getMedian());
6464

6565
stream.insert(1);
66-
assertEquals(17, stream.median());
66+
assertEquals(17, stream.getMedian());
6767
}
6868

6969
@Test
7070
public void testWithNegativeAndPositiveValues() {
7171
var stream = new MedianOfRunningArrayInteger();
7272
stream.insert(-1);
73-
assertEquals(-1, stream.median());
73+
assertEquals(-1, stream.getMedian());
7474
stream.insert(2);
75-
assertEquals(0, stream.median());
75+
assertEquals(0, stream.getMedian());
7676
stream.insert(-3);
77-
assertEquals(-1, stream.median());
77+
assertEquals(-1, stream.getMedian());
7878
}
7979

8080
@Test
8181
public void testWithDuplicateValues() {
8282
var stream = new MedianOfRunningArrayInteger();
8383
stream.insert(-1);
84-
assertEquals(-1, stream.median());
84+
assertEquals(-1, stream.getMedian());
8585
stream.insert(-1);
86-
assertEquals(-1, stream.median());
86+
assertEquals(-1, stream.getMedian());
8787
stream.insert(-1);
88-
assertEquals(-1, stream.median());
88+
assertEquals(-1, stream.getMedian());
8989
}
9090

9191
@Test
@@ -98,20 +98,20 @@ public void testWithDuplicateValuesB() {
9898
stream.insert(20);
9999
stream.insert(0);
100100
stream.insert(50);
101-
assertEquals(10, stream.median());
101+
assertEquals(10, stream.getMedian());
102102
}
103103

104104
@Test
105105
public void testWithLargeValues() {
106106
var stream = new MedianOfRunningArrayInteger();
107107
stream.insert(1000000);
108-
assertEquals(1000000, stream.median());
108+
assertEquals(1000000, stream.getMedian());
109109
stream.insert(12000);
110-
assertEquals(506000, stream.median());
110+
assertEquals(506000, stream.getMedian());
111111
stream.insert(15000000);
112-
assertEquals(1000000, stream.median());
112+
assertEquals(1000000, stream.getMedian());
113113
stream.insert(2300000);
114-
assertEquals(1650000, stream.median());
114+
assertEquals(1650000, stream.getMedian());
115115
}
116116

117117
@Test
@@ -120,7 +120,7 @@ public void testWithLargeCountOfValues() {
120120
for (int i = 1; i <= 1000; i++) {
121121
stream.insert(i);
122122
}
123-
assertEquals(500, stream.median());
123+
assertEquals(500, stream.getMedian());
124124
}
125125

126126
@Test
@@ -129,7 +129,7 @@ public void testWithThreeValuesInDescendingOrder() {
129129
stream.insert(30);
130130
stream.insert(20);
131131
stream.insert(10);
132-
assertEquals(20, stream.median());
132+
assertEquals(20, stream.getMedian());
133133
}
134134

135135
@Test
@@ -138,7 +138,7 @@ public void testWithThreeValuesInOrder() {
138138
stream.insert(10);
139139
stream.insert(20);
140140
stream.insert(30);
141-
assertEquals(20, stream.median());
141+
assertEquals(20, stream.getMedian());
142142
}
143143

144144
@Test
@@ -147,7 +147,7 @@ public void testWithThreeValuesNotInOrderA() {
147147
stream.insert(30);
148148
stream.insert(10);
149149
stream.insert(20);
150-
assertEquals(20, stream.median());
150+
assertEquals(20, stream.getMedian());
151151
}
152152

153153
@Test
@@ -156,46 +156,46 @@ public void testWithThreeValuesNotInOrderB() {
156156
stream.insert(20);
157157
stream.insert(10);
158158
stream.insert(30);
159-
assertEquals(20, stream.median());
159+
assertEquals(20, stream.getMedian());
160160
}
161161

162162
@Test
163163
public void testWithFloatValues() {
164164
var stream = new MedianOfRunningArrayFloat();
165165
stream.insert(20.0f);
166-
assertEquals(20.0f, stream.median());
166+
assertEquals(20.0f, stream.getMedian());
167167
stream.insert(10.5f);
168-
assertEquals(15.25f, stream.median());
168+
assertEquals(15.25f, stream.getMedian());
169169
stream.insert(30.0f);
170-
assertEquals(20.0f, stream.median());
170+
assertEquals(20.0f, stream.getMedian());
171171
}
172172

173173
@Test
174174
public void testWithByteValues() {
175175
var stream = new MedianOfRunningArrayByte();
176176
stream.insert((byte) 120);
177-
assertEquals((byte) 120, stream.median());
177+
assertEquals((byte) 120, stream.getMedian());
178178
stream.insert((byte) -120);
179-
assertEquals((byte) 0, stream.median());
179+
assertEquals((byte) 0, stream.getMedian());
180180
stream.insert((byte) 127);
181-
assertEquals((byte) 120, stream.median());
181+
assertEquals((byte) 120, stream.getMedian());
182182
}
183183

184184
@Test
185185
public void testWithLongValues() {
186186
var stream = new MedianOfRunningArrayLong();
187187
stream.insert(120000000L);
188-
assertEquals(120000000L, stream.median());
188+
assertEquals(120000000L, stream.getMedian());
189189
stream.insert(92233720368547757L);
190-
assertEquals(46116860244273878L, stream.median());
190+
assertEquals(46116860244273878L, stream.getMedian());
191191
}
192192

193193
@Test
194194
public void testWithDoubleValues() {
195195
var stream = new MedianOfRunningArrayDouble();
196196
stream.insert(12345.67891);
197-
assertEquals(12345.67891, stream.median());
197+
assertEquals(12345.67891, stream.getMedian());
198198
stream.insert(23456789.98);
199-
assertEquals(11734567.83, stream.median(), .01);
199+
assertEquals(11734567.83, stream.getMedian(), .01);
200200
}
201201
}

0 commit comments

Comments
 (0)