Find K largest elements in array using Min Heap.

Find K largest elements in array using Min Heap.

---

Given a unsorted array, Find k largest element in array.

Find K largest elements in array using Max Heap

Lets understand what is the input and the expected output.

Algorithm (We will use Min Heap for getting K largest element)

---

In the previous post we saw Find K largest elements in array using Max Heap, In this post we will see how to get K largest elements using Min heap.

How Heapify works : Heap Sort Algorithm

1. We are interested in k largest element in array, for this we will first pick first K elements and build Min Heap of first K elements that will bring lowest elements at root that is at arr[0].
2. So say if the array is {4, 10, 3, 5, 1}; and k=3 then we will first build min heap of initial 3 elements {4, 10, 3} 
3. After heapify process, array will be {1,4,3,5,10}, Note: lowest element is at array[0]
4. Now, we will iterate remaining elements(in our case {5,10}) from k+1 till array length, and see 
1. If we get maximum element than arr[0], it means arr[0] should be replaced by that value as arr[0] is lowest one. After replacing we again want our arr[0] to contain minimum of first K element, so we will call heapify process for arr[0].
2. If we get minimum element than arr[0], then we don't care as we are only interested in max elements.
3. At the end, first K elements of array would contain maximum elements of whole array.
5. Though first K elements would contain max element present in whole array, but they won't be in sorted order, if sorted order is expected then we need to use some sorting algorithm to sort first K elements.

There are several ways to get the K largest elements, Here I particularly want to show Min Heap approach.

Find K Largest element in array using Min Heap

---

package com.javabypatel.heap;

public class FindMaxKElementInArray {
    public static void main(String[] args) {
        int[] array = new int[] {4, 10, 3, 5, 1};

        int k = 3;
        new FindMaxKElementInArray().printMaxKElements(array, k);
        for (int i = 0; i < k; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public void printMaxKElements(int data[], int k) {
        if(k > data.length) {
            System.out.println("Invalid k size");
            return;
        }
        /*
            {4, 10, 3, 5, 1}

                  4
                /  \
               10  3
              / \
             5  1
         */
        //We are taking first k elements {4,10,3} and get the minimum at root that is at data[0]
        for (int i = k - 1; i >= 0; i--) {
            minHeapify(i, data, data.length);
        }
        //At this stage our initial k size array will be {1,4,3,5,10} minimum among first k element is at arr[0]

        //this says if say we have only 3 element in array and if k is 3, then {1,4,3} is answer
        //in this case, we have to work for remaining {5,10}, lets see if we can get maximum from them.

        //Remember our root is minimum one among first k elements, so while iterating for k+1 till end that is {5,10}
        //if we get maximum element than arr[0], it means arr[0] should be replaced by that value as arr[0] is lowest and
            //we found max than that. After replacing we again want our arr[0] to contain minimum of first K element, so we will again
            //call heapify process for first K element and that will bring minimum back to arr[0] for next comparison.
        //if we get minimum element than arr[0], then we don't care as we are only interested in max elements.
        //At the end, first K elements of array would contain maximum elements of whole array.

        //Start from k till end and see if we find element greater than arr[0]
        for (int i = k; i < data.length; i++) {
            if(data[0] < data[i]) {
                //Found some data greater than arr[0], replace that with nex max.
                data[0] = data[i];

                //Call heapify process for firsst K elements and that will bring minimum among k elements back to arr[0]
                minHeapify(0, data, k);
            }
        }

        //first K elements will have maximum elements of array.
        //Note this first K maximum elements wont be in sorted order, so if require, sort the first K elements.
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

    private int rightChild(int i) {
        return 2 * i + 2;
    }

    private void minHeapify(int i, int[] data, int size) {
        int smallestElementIndex = i;

        int leftChildIndex = leftChild(i);
        if (leftChildIndex < size && data[leftChildIndex] < data[smallestElementIndex]) {
            smallestElementIndex = leftChildIndex;
        }

        int rightChildIndex = rightChild(i);
        if (rightChildIndex < size && data[rightChildIndex] < data[smallestElementIndex]) {
            smallestElementIndex = rightChildIndex;
        }

        if (smallestElementIndex != i) {
            int swap = data[i];
            data[i] = data[smallestElementIndex];
            data[smallestElementIndex] = swap;

            // Recursively heapify for the affected node
            minHeapify(smallestElementIndex, data, size);
        }
    }
}

Find K Largest element in array using PriorityQueue

package com.javabypatel.heap;

import java.util.PriorityQueue;

public class FindMaxKElementInArray {
    public static void main(String[] args) {
        int[] array = new int[] {4, 10, 3, 5, 1};
        System.out.println(new FindMaxKElementInArray().findKthLargest(array, 2));
    }

    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
        for (int i : nums) {
            q.offer(i);

            if (q.size() > k) {
                q.poll();
            }
        }
        System.out.println(q); //To print all k Largest elements
        return q.peek(); //To print kth Largest element
    }
}

Output:
[5, 10]
5

You may also like to see

---

Sort Linked list using Merge sort

Bubble Sort

Heap Sort

Selection Sort

Insertion Sort

---

How ConcurrentHashMap works and ConcurrentHashMap interview questions

How Much Water Can A Bar Graph with different heights can Hold

Interview Questions-Answer Bank

Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.