Top k elements in an array

helga_sh · helga_sh · commit 04e1e1b2ab5b · 2020-07-06T17:48:09.000+03:00
diff --git a/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/BruteForceTopKElementsFinder.java b/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/BruteForceTopKElementsFinder.java
@@ -0,0 +1,26 @@
+package com.baeldung.algorithms.topnelements;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class BruteForceTopKElementsFinder implements TopKElementsFinder<Integer> {
+
+    public List<Integer> findTopK(List<Integer> input, int k) {
+        List<Integer> array = new ArrayList<>(input);
+        List<Integer> topKList = new ArrayList<>();
+
+        for (int i = 0; i < k; i++) {
+            int maxIndex = 0;
+
+            for (int j = 1; j < array.size(); j++) {
+                if (array.get(j) > array.get(maxIndex)) {
+                    maxIndex = j;
+                }
+            }
+
+            topKList.add(array.remove(maxIndex));
+        }
+
+        return topKList;
+    }
+}
diff --git a/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/MaxHeapTopKElementsFinder.java b/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/MaxHeapTopKElementsFinder.java
@@ -0,0 +1,26 @@
+package com.baeldung.algorithms.topnelements;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+import java.util.PriorityQueue;
+
+public class MaxHeapTopKElementsFinder implements TopKElementsFinder<Integer> {
+
+    public List<Integer> findTopK(List<Integer> input, int k) {
+        PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
+
+        input.forEach(number -> {
+            maxHeap.add(number);
+
+            if (maxHeap.size() > k) {
+                maxHeap.poll();
+            }
+        });
+
+        List<Integer> topKList = new ArrayList<>(maxHeap);
+        Collections.reverse(topKList);
+
+        return topKList;
+    }
+}
diff --git a/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/TopKElementsFinder.java b/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/TopKElementsFinder.java
@@ -0,0 +1,7 @@
+package com.baeldung.algorithms.topnelements;
+
+import java.util.List;
+
+public interface TopKElementsFinder<T extends Comparable<T>> {
+    List<T> findTopK(List<T> input, int k);
+}
diff --git a/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/TreeSetTopKElementsFinder.java b/algorithms-miscellaneous-6/src/main/java/com/baeldung/algorithms/topnelements/TreeSetTopKElementsFinder.java
@@ -0,0 +1,17 @@
+package com.baeldung.algorithms.topnelements;
+
+import java.util.Comparator;
+import java.util.List;
+import java.util.Set;
+import java.util.TreeSet;
+import java.util.stream.Collectors;
+
+public class TreeSetTopKElementsFinder implements TopKElementsFinder<Integer> {
+
+    public List<Integer> findTopK(List<Integer> input, int k) {
+        Set<Integer> sortedSet = new TreeSet<>(Comparator.reverseOrder());
+        sortedSet.addAll(input);
+
+        return sortedSet.stream().limit(k).collect(Collectors.toList());
+    }
+}
diff --git a/algorithms-miscellaneous-6/src/test/java/com/baeldung/algorithms/topkelements/TopKElementsFinderUnitTest.java b/algorithms-miscellaneous-6/src/test/java/com/baeldung/algorithms/topkelements/TopKElementsFinderUnitTest.java
@@ -0,0 +1,50 @@
+package com.baeldung.algorithms.topkelements;
+
+import com.baeldung.algorithms.topnelements.BruteForceTopKElementsFinder;
+import com.baeldung.algorithms.topnelements.MaxHeapTopKElementsFinder;
+import com.baeldung.algorithms.topnelements.TopKElementsFinder;
+import com.baeldung.algorithms.topnelements.TreeSetTopKElementsFinder;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.List;
+
+import static org.assertj.core.api.Java6Assertions.assertThat;
+
+public class TopKElementsFinderUnitTest {
+    private final TopKElementsFinder<Integer> bruteForceFinder = new BruteForceTopKElementsFinder();
+    private final TopKElementsFinder<Integer> maxHeapFinder = new MaxHeapTopKElementsFinder();
+    private final TopKElementsFinder<Integer> treeSetFinder = new TreeSetTopKElementsFinder();
+
+    private final int k = 4;
+    private final List<Integer> distinctIntegers = Arrays.asList(1, 2, 3, 9, 7, 6, 12);
+    private final List<Integer> distinctIntegersTopK = Arrays.asList(9, 7, 6, 12);
+    private final List<Integer> nonDistinctIntegers = Arrays.asList(1, 2, 3, 3, 9, 9, 7, 6, 12);
+    private final List<Integer> nonDistinctIntegersTopK = Arrays.asList(9, 9, 7, 12);
+
+
+    @Test
+    public void givenArrayDistinctIntegers_whenBruteForceFindTopK_thenReturnKLargest() {
+        assertThat(bruteForceFinder.findTopK(distinctIntegers, k)).containsOnlyElementsOf(distinctIntegersTopK);
+    }
+
+    @Test
+    public void givenArrayDistinctIntegers_whenMaxHeapFindTopK_thenReturnKLargest() {
+        assertThat(maxHeapFinder.findTopK(distinctIntegers, k)).containsOnlyElementsOf(distinctIntegersTopK);
+    }
+
+    @Test
+    public void givenArrayDistinctIntegers_whenTreeSetFindTopK_thenReturnKLargest() {
+        assertThat(treeSetFinder.findTopK(distinctIntegers, k)).containsOnlyElementsOf(distinctIntegersTopK);
+    }
+
+    @Test
+    public void givenArrayNonDistinctIntegers_whenBruteForceFindTopK_thenReturnKLargest() {
+        assertThat(bruteForceFinder.findTopK(nonDistinctIntegers, k)).containsOnlyElementsOf(nonDistinctIntegersTopK);
+    }
+
+    @Test
+    public void givenArrayNonDistinctIntegers_whenMaxHeapFindTopK_thenReturnKLargest() {
+        assertThat(maxHeapFinder.findTopK(nonDistinctIntegers, k)).containsOnlyElementsOf(nonDistinctIntegersTopK);
+    }
+}
