Trusted answers to developer questions
Find the kth smallest element from an array using a min-heap
Finding the smallest element of an array efficiently may seem a little tricky at first. However, it can be found easily using a min-heap or by sorting the array.
Algorithm
The following steps are involved in finding the smallest element using a min-heap.
-
Create a min-heap using the given array.
-
Remove the element at the root of the heap times.
-
The element on the root of the heap is the smallest element.
The illustration below further explains this concept.
Consider the array above.
1 of 6
Implementation
The following code snippet implements the above algorithm in C++.
#include <bits/stdc++.h>using namespace std;int main (){// Creating a min-heap.priority_queue <int, vector<int>, greater<int> > minheap;minheap.push(10);minheap.push(1);minheap.push(0);minheap.push(8);minheap.push(7);minheap.push(2);// Removing the element at the root of the min-heap k-1 times.for(int i = 0; i < 2; i++){minheap.pop();}// Displaying the element at the root of the min-heap.cout<<"The third smallest element in the given array is: "<<minheap.top() << endl;return 0;}
RELATED TAGS
data structures
heap
Copyright ©2024 Educative, Inc. All rights reserved
TRENDING TOPICS
Did you find this helpful?