Repository: TheAlgorithms/Java
Pull request #5836 (2024-10-15 06:49:23)

feat: Add `KthElementFinder` 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/5836?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `92.30769%` with `1 line` in your changes missing coverage. Please review.
> Project coverage is 66.01%. Comparing base [(`30504c1`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/30504c179ebc42d15c7b738435a87a3d8bc4053b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`4d7bf7a`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/4d7bf7ac7b92cfe5650ab4582520d91d25683c88?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files with missing lines](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5836?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...orithms/datastructures/heaps/KthElementFinder.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5836?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fdatastructures%2Fheaps%2FKthElementFinder.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9kYXRhc3RydWN0dXJlcy9oZWFwcy9LdGhFbGVtZW50RmluZGVyLmphdmE=) | 92.30% | [1 Missing :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5836?src=pr&el=tree&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    #5836      +/-   ##
============================================
+ Coverage     65.99%   66.01%   +0.02%     
- Complexity     4395     4399       +4     
============================================
  Files           603      604       +1     
  Lines         16799    16812      +13     
  Branches       3226     3230       +4     
============================================
+ Hits          11086    11098      +12     
- Misses         5266     5267       +1     
  Partials        447      447              
```

</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5836?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 8edcb19d..a5d3a1a2 100644
--- a/DIRECTORY.md
+++ b/DIRECTORY.md
@@ -174,6 +174,7 @@
               * [GenericHeap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/GenericHeap.java)
               * [Heap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/Heap.java)
               * [HeapElement](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/HeapElement.java)
+              * [KthElementFinder](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java)
               * [LeftistHeap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java)
               * [MaxHeap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java)
               * [MinHeap](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java)
@@ -848,6 +849,7 @@
             * heaps
               * [FibonacciHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/FibonacciHeapTest.java)
               * [GenericHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/GenericHeapTest.java)
+              * [KthElementFinderTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/KthElementFinderTest.java)
               * [LeftistHeapTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/LeftistHeapTest.java)
               * [MinPriorityQueueTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/datastructures/heaps/MinPriorityQueueTest.java)
             * lists
diff --git a/src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java b/src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java
new file mode 100644
index 00000000..7ad92e8b
--- /dev/null
+++ b/src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java
@@ -0,0 +1,60 @@
+
+package com.thealgorithms.datastructures.heaps;
+
+import java.util.PriorityQueue;
+
+/**
+ * This class provides methods to find the Kth largest or Kth smallest element
+ * in an array using heaps. It leverages a min-heap to find the Kth largest element
+ * and a max-heap to find the Kth smallest element efficiently.
+ *
+ * @author Hardvan
+ */
+public final class KthElementFinder {
+    private KthElementFinder() {
+    }
+
+    /**
+     * Finds the Kth largest element in the given array.
+     * Uses a min-heap of size K to track the largest K elements.
+     *
+     * Time Complexity: O(n * log(k)), where n is the size of the input array.
+     * Space Complexity: O(k), as we maintain a heap of size K.
+     *
+     * @param nums the input array of integers
+     * @param k the desired Kth position (1-indexed, i.e., 1 means the largest element)
+     * @return the Kth largest element in the array
+     */
+    public static int findKthLargest(int[] nums, int k) {
+        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
+        for (int num : nums) {
+            minHeap.offer(num);
+            if (minHeap.size() > k) {
+                minHeap.poll();
+            }
+        }
+        return minHeap.peek();
+    }
+
+    /**
+     * Finds the Kth smallest element in the given array.
+     * Uses a max-heap of size K to track the smallest K elements.
+     *
+     * Time Complexity: O(n * log(k)), where n is the size of the input array.
+     * Space Complexity: O(k), as we maintain a heap of size K.
+     *
+     * @param nums the input array of integers
+     * @param k the desired Kth position (1-indexed, i.e., 1 means the smallest element)
+     * @return the Kth smallest element in the array
+     */
+    public static int findKthSmallest(int[] nums, int k) {
+        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
+        for (int num : nums) {
+            maxHeap.offer(num);
+            if (maxHeap.size() > k) {
+                maxHeap.poll();
+            }
+        }
+        return maxHeap.peek();
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/datastructures/heaps/KthElementFinderTest.java b/src/test/java/com/thealgorithms/datastructures/heaps/KthElementFinderTest.java
new file mode 100644
index 00000000..7b92a57e
--- /dev/null
+++ b/src/test/java/com/thealgorithms/datastructures/heaps/KthElementFinderTest.java
@@ -0,0 +1,19 @@
+package com.thealgorithms.datastructures.heaps;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.jupiter.api.Test;
+
+public class KthElementFinderTest {
+    @Test
+    public void testFindKthLargest() {
+        int[] nums = {3, 2, 1, 5, 6, 4};
+        assertEquals(5, KthElementFinder.findKthLargest(nums, 2));
+    }
+
+    @Test
+    public void testFindKthSmallest() {
+        int[] nums = {7, 10, 4, 3, 20, 15};
+        assertEquals(7, KthElementFinder.findKthSmallest(nums, 3));
+    }
+}