Repository: TheAlgorithms/Java
Pull request #4384 (2023-09-20 07:10:06)

#4382 Bug Fix
Fixed The Bug for the Test Case mentioned in linked Issue as well as made code more readable


govardhanshah456: Hey, i have made requested changes, please have a look into it.
govardhanshah456: Hey, as you said its out of scope for this PR, what we can do instead is we can make new enhancement issue of making Median Generic and then work on it, that would appear more appropriate, and yes median would always be double for instance, (1,2) median would be (1+2)/2 which is double although input is int array.

Patch:
diff --git a/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java b/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java
index 84dff89e..61fbfa82 100644
--- a/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java
+++ b/src/main/java/com/thealgorithms/misc/MedianOfRunningArray.java
@@ -8,13 +8,13 @@ import java.util.PriorityQueue;
  */
 public class MedianOfRunningArray {
 
-    private PriorityQueue<Integer> p1;
-    private PriorityQueue<Integer> p2;
+    private PriorityQueue<Integer> maxHeap;
+    private PriorityQueue<Integer> minHeap;
 
     // Constructor
     public MedianOfRunningArray() {
-        this.p1 = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap
-        this.p2 = new PriorityQueue<>(); // Min Heap
+        this.maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max Heap
+        this.minHeap = new PriorityQueue<>(); // Min Heap
     }
 
     /*
@@ -22,32 +22,30 @@ public class MedianOfRunningArray {
       and upper half to min heap
      */
     public void insert(Integer e) {
-        p2.add(e);
-        if (p2.size() - p1.size() > 1) {
-            p1.add(p2.remove());
+        if (!minHeap.isEmpty() && e < minHeap.peek()) {
+            maxHeap.offer(e);
+            if (maxHeap.size() > minHeap.size() + 1) {
+                minHeap.offer(maxHeap.poll());
+            }
+        } else {
+            minHeap.offer(e);
+            if (minHeap.size() > maxHeap.size() + 1) {
+                maxHeap.offer(minHeap.poll());
+            }
         }
     }
 
     /*
       Returns median at any given point
      */
-    public Integer median() {
-        if (p1.size() == p2.size()) {
-            return (p1.peek() + p2.peek()) / 2;
+    public double median() {
+        if (maxHeap.isEmpty() && minHeap.isEmpty()) {
+            throw new IllegalArgumentException("Enter at least 1 element, Median of empty list is not defined!");
         }
-        return p1.size() > p2.size() ? p1.peek() : p2.peek();
-    }
-
-    public static void main(String[] args) {
-        /*
-        Testing the median function
-         */
 
-        MedianOfRunningArray p = new MedianOfRunningArray();
-        int[] arr = {10, 7, 4, 9, 2, 3, 11, 17, 14};
-        for (int i = 0; i < 9; i++) {
-            p.insert(arr[i]);
-            System.out.print(p.median() + " ");
+        if (maxHeap.size() == minHeap.size()) {
+            return (maxHeap.peek() + minHeap.peek()) / 2.0;
         }
+        return maxHeap.size() > minHeap.size() ? maxHeap.peek() * 1.0 : minHeap.peek() * 1.0;
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java b/src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java
new file mode 100644
index 00000000..96cdc77e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/misc/MedianOfRunningArrayTest.java
@@ -0,0 +1,161 @@
+package com.thealgorithms.misc;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertFalse;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+import org.apache.commons.lang3.tuple.Pair;
+import org.junit.jupiter.api.Test;
+
+/**
+ * Test case for Two sum Problem.
+ * @author Bama Charan Chhandogi (https://github.com/BamaCharanChhandogi)
+ */
+
+public class MedianOfRunningArrayTest {
+    private static final String EXCEPTION_MESSAGE = "Enter at least 1 element, Median of empty list is not defined!";
+
+    @Test
+    public void testWhenInvalidInoutProvidedShouldThrowException() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        IllegalArgumentException exception = assertThrows(IllegalArgumentException.class, () -> stream.median());
+        assertEquals(exception.getMessage(), EXCEPTION_MESSAGE);
+    }
+
+    @Test
+    public void testWithNegativeValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(-1);
+        assertEquals(-1, stream.median());
+        stream.insert(-2);
+        assertEquals(-1.5, stream.median());
+        stream.insert(-3);
+        assertEquals(-2, stream.median());
+    }
+
+    @Test
+    public void testWithSingleValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(-1);
+        assertEquals(-1, stream.median());
+    }
+
+    @Test
+    public void testWithRandomValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(10);
+        assertEquals(10.0, stream.median());
+
+        stream.insert(5);
+        assertEquals(7.5, stream.median());
+
+        stream.insert(20);
+        assertEquals(10.0, stream.median());
+
+        stream.insert(15);
+        assertEquals(12.5, stream.median());
+
+        stream.insert(25);
+        assertEquals(15.0, stream.median());
+
+        stream.insert(30);
+        assertEquals(17.5, stream.median());
+
+        stream.insert(35);
+        assertEquals(20.0, stream.median());
+
+        stream.insert(1);
+        assertEquals(17.5, stream.median());
+    }
+
+    @Test
+    public void testWithNegativeAndPositiveValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(-1);
+        assertEquals(-1, stream.median());
+        stream.insert(2);
+        assertEquals(0.5, stream.median());
+        stream.insert(-3);
+        assertEquals(-1, stream.median());
+    }
+
+    @Test
+    public void testWithDuplicateValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(-1);
+        assertEquals(-1, stream.median());
+        stream.insert(-1);
+        assertEquals(-1, stream.median());
+        stream.insert(-1);
+        assertEquals(-1, stream.median());
+    }
+
+    @Test
+    public void testWithDuplicateValuesB() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(10);
+        stream.insert(20);
+        stream.insert(10);
+        stream.insert(10);
+        stream.insert(20);
+        stream.insert(0);
+        stream.insert(50);
+        assertEquals(10, stream.median());
+    }
+
+    @Test
+    public void testWithLargeValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(1000000);
+        assertEquals(1000000, stream.median());
+        stream.insert(12000);
+        assertEquals(506000, stream.median());
+        stream.insert(15000000);
+        assertEquals(1000000, stream.median());
+        stream.insert(2300000);
+        assertEquals(1650000.00, stream.median());
+    }
+
+    @Test
+    public void testWithLargeCountOfValues() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        for (int i = 1; i <= 1000; i++) stream.insert(i);
+        assertEquals(500.5, stream.median());
+    }
+
+    @Test
+    public void testWithThreeValuesInDescendingOrder() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(30);
+        stream.insert(20);
+        stream.insert(10);
+        assertEquals(20.0, stream.median());
+    }
+
+    @Test
+    public void testWithThreeValuesInOrder() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(10);
+        stream.insert(20);
+        stream.insert(30);
+        assertEquals(20.0, stream.median());
+    }
+
+    @Test
+    public void testWithThreeValuesNotInOrderA() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(30);
+        stream.insert(10);
+        stream.insert(20);
+        assertEquals(20.0, stream.median());
+    }
+
+    @Test
+    public void testWithThreeValuesNotInOrderB() {
+        MedianOfRunningArray stream = new MedianOfRunningArray();
+        stream.insert(20);
+        stream.insert(10);
+        stream.insert(30);
+        assertEquals(20.0, stream.median());
+    }
+}