Be the first user to complete this post

  • 0
Add to List
Beginner

155. Find the Kth Smallest/Largest Element in an Array Using Heap

Objective: Given an array of integers. find the Kth Smallest/largest element in the array.

Example

int[] A = { 1, 2, 10, 20, 40, 32, 44, 51, 6 };

K=4th smallest element in given array: 10

Approach: (Kth Smallest Element)

  • Use min-Heap. (Click here to read about Priority Queue).
  • Insert all the elements in the Priority Queue.
  • Extract K elements from the priority queue. The last element (kth) extracted with be the kth smallest element in the array.

Output:

Output:
4th smallest element:10

Note: For kth largest element, implement priority queue for max-Heap.