K’th Least Element in a Min-Heap in C++

In this tutorial, we are going to write a program that finds the k-th least element from the min-heap.

We will use priority queue to solve the problem. Let's see the steps to complete the program.

• Initialise the min-heap with correct values.
• Create a priority queue and insert the root node of the min-heap.
• Write a loop that iterates k - 1 times.
  • Pop the least element from the queue.
  • Add the left and right nodes of the above node into the priority queue.
• The greatest element in priority queue is the k-th greatest element now.
• Return it.

Example

Let's see the code.

 Live Demo

#include <bits/stdc++.h> using namespace std; struct Heap {    vector<int> elemets;    int n;    Heap(int i = 0): n(i) {       elemets = vector<int>(n);    } }; inline int leftIndex(int i) {    return 2 * i + 1; } inline int rightIndex(int i) {    return 2 * i + 2; } int findKthGreatestElement(Heap &heap, int k) {    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>queue;    queue.push(make_pair(heap.elemets[0], 0));    for (int i = 0; i < k - 1; ++i) {       int node = queue.top().second;       queue.pop();       int left = leftIndex(node), right = rightIndex(node);       if (left < heap.n) {          queue.push(make_pair(heap.elemets[left], left));       }       if (right < heap.n) {          queue.push(make_pair(heap.elemets[right], right));       }    }    return queue.top().first; } int main() {    Heap heap(10);    heap.elemets = vector<int>{ 10, 14, 19, 24, 32, 41, 27, 44, 35, 33 };    cout << findKthGreatestElement(heap, 4) << endl;    return 0; }

Output

If you run the above code, then you will get the following result.

24

Conclusion

If you have any queries in the tutorial, mention them in the comment section.