Find K largest elements in array using Max Heap

Find K largest elements in array using Max Heap.

---

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

Heap Sort Algorithm

Lets understand what is the input and the expected output.

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

---

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

How Heapify works : Heap Sort Algorithm

1. First we will build a heap which requires O(n) time for building the heap.
2. Once the heap is build, largest element would be at the root or at arr[0].
3. Print the max at arr[0], swap max at arr[0] with the last element of heap.
4. Heapify the tree K times to get max K elements.

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

Find K Largest element in array using Max Heap

---

package com.javabypatel.heap;

/*

Input:
    array = [4, 10, 3, 5, 1]    K = 2
Output:
    10 5

Input:
    array = [4, 10, 3, 5, 1]    K = 5

Output: 10 5 4 3 1

Input:
    array = [4, 10, 3, 5, 1]    K = 0

Output:

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

    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
         */
         
        //This step is called building a Heap
        for (int i = data.length/2 -1; i >= 0; i--) {
            maxHeapify(i, data, data.length);
        }

        //Once the heap is build by above step, we replace the max element at arr[0](root element) to last index of array
        //and decrease the size by 1 in next iteration as highest element is already at its place.
        //Remember in each iteration we would have highest element at arr[0] and we will swap it to last element of heap size.
        //so for finding the Kth largest element, we will only need to swap k times.
        for (int i = data.length - 1; i >= data.length - k; i--) {
            System.out.print(data[0] + " ");

            //Swap max element at root(arr[0] to last element)
            int temp = data[0];
            data[0] = data[i];
            data[i] = temp;

            //swapping would have disturbed the heap property,
            //so calling max heapify for index 0 on the reduced heap size.
            //if we pass i in place of size should also work as that also represents the size
            maxHeapify(0, data, i);
        }
    }

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

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

    private void maxHeapify(int i, int[] data, int size) {
        int largestElementIndex = i;

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

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

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

            // Recursively heapify for the affected node
            maxHeapify(largestElementIndex, 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.