Repository: TheAlgorithms/Java
Pull request #5805 (2024-10-14 10:02:22)

feat: Add `OptimalFileMerging` new algorithm with Junit tests
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5805?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
All modified and coverable lines are covered by tests :white_check_mark:
> Project coverage is 64.83%. Comparing base [(`9c76b30`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/9c76b30271535123ea30c0b39a46ccee6b302c6c?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`ad57403`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/ad574030cd04e3cb284f603f51a90c4b7edd43f5?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5805      +/-   ##
============================================
+ Coverage     64.81%   64.83%   +0.02%     
- Complexity     4299     4302       +3     
============================================
  Files           599      600       +1     
  Lines         16764    16776      +12     
  Branches       3219     3221       +2     
============================================
+ Hits          10865    10877      +12     
  Misses         5455     5455              
  Partials        444      444              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5805?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).


Patch:
diff --git a/DIRECTORY.md b/DIRECTORY.md
index ee1b9dcd..d2badd76 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -328,6 +328,7 @@
             * [MergeIntervals](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/MergeIntervals.java)
             * [MinimizingLateness](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/MinimizingLateness.java)
             * [MinimumWaitingTime](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/MinimumWaitingTime.java)
+            * [OptimalFileMerging](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/OptimalFileMerging.java)
             * [StockProfitCalculator](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/StockProfitCalculator.java)
           * io
             * [BufferedReader](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/io/BufferedReader.java)
@@ -956,6 +957,7 @@
             * [MergeIntervalsTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/MergeIntervalsTest.java)
             * [MinimizingLatenessTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/MinimizingLatenessTest.java)
             * [MinimumWaitingTimeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/MinimumWaitingTimeTest.java)
+            * [OptimalFileMergingTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/OptimalFileMergingTest.java)
             * [StockProfitCalculatorTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/StockProfitCalculatorTest.java)
           * io
             * [BufferedReaderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/io/BufferedReaderTest.java)
diff --git a/src/main/java/com/thealgorithms/greedyalgorithms/OptimalFileMerging.java b/src/main/java/com/thealgorithms/greedyalgorithms/OptimalFileMerging.java
new file mode 100644
index 00000000..7a1f2edf
--- /dev/null
+++ b/src/main/java/com/thealgorithms/greedyalgorithms/OptimalFileMerging.java
@@ -0,0 +1,52 @@
+package com.thealgorithms.greedyalgorithms;
+
+import java.util.PriorityQueue;
+
+/**
+ * Class to solve the Optimal File Merging Problem.
+ * The goal is to minimize the cost of merging files, where the cost of merging two files is the sum of their sizes.
+ * The cost of merging all files is the sum of the costs of merging each pair of files.
+ * Example:
+ * files = [4, 3, 2, 6]
+ * The minimum cost to merge all files is 29.
+ * Steps:
+ * 1. Merge files 2 and 3 (cost = 2 + 3 = 5). New files = [4, 5, 6]
+ * 2. Merge files 4 and 5 (cost = 4 + 5 = 9). New files = [6, 9]
+ * 3. Merge files 6 and 9 (cost = 6 + 9 = 15). New files = [15]
+ * Total cost = 5 + 9 + 15 = 29
+ *
+ * @author Hardvan
+ */
+public final class OptimalFileMerging {
+    private OptimalFileMerging() {
+    }
+
+    /**
+     * Calculates the minimum cost to merge all files.
+     * Steps:
+     * 1. Add all files to a min heap.
+     * 2. Remove the two smallest files from the heap, merge them, and add the result back to the heap.
+     * 3. Repeat step 2 until there is only one file left in the heap.
+     * 4. The total cost is the sum of all the costs of merging the files.
+     *
+     * @param files array of file sizes
+     * @return the minimum cost to merge the files
+     */
+    public static int minMergeCost(int[] files) {
+        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
+        for (int file : files) {
+            minHeap.add(file);
+        }
+
+        int totalCost = 0;
+        while (minHeap.size() > 1) {
+            int first = minHeap.poll();
+            int second = minHeap.poll();
+            int cost = first + second;
+            totalCost += cost;
+
+            minHeap.add(cost);
+        }
+        return totalCost;
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/greedyalgorithms/OptimalFileMergingTest.java b/src/test/java/com/thealgorithms/greedyalgorithms/OptimalFileMergingTest.java
new file mode 100644
index 00000000..9ff2b95f
--- /dev/null
+++ b/src/test/java/com/thealgorithms/greedyalgorithms/OptimalFileMergingTest.java
@@ -0,0 +1,22 @@
+package com.thealgorithms.greedyalgorithms;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class OptimalFileMergingTest {
+
+    @ParameterizedTest
+    @MethodSource("fileMergingProvider")
+    public void testMinMergeCost(int[] files, int expected) {
+        assertEquals(expected, OptimalFileMerging.minMergeCost(files));
+    }
+
+    private static Stream<Arguments> fileMergingProvider() {
+        return Stream.of(Arguments.of(new int[] {4, 3, 2, 6}, 29), Arguments.of(new int[] {5}, 0), Arguments.of(new int[] {2, 2, 2}, 10), Arguments.of(new int[] {10, 5, 3, 2}, 35), Arguments.of(new int[] {1, 1, 1, 1}, 8), Arguments.of(new int[] {1, 2, 3, 4, 5}, 33),
+            Arguments.of(new int[] {1, 2, 3, 4, 5, 6}, 51), Arguments.of(new int[] {1, 2, 3, 4, 5, 6, 7}, 74), Arguments.of(new int[] {1, 2, 3, 4, 5, 6, 7, 8}, 102), Arguments.of(new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9}, 135));
+    }
+}