Kth smallest element after every insertion in C++

In this tutorial, we are going to find the k-th smallest element after every insertion.

We are going to use the min-heap to solve the problem. Let's see the steps to complete the program.

• Initialise the array with random data.
• Initialise the priority queue.
• Till k - 1 there won't be any k-th smallest element. So, print any symbol u like.
• Write a loop that iterates from k + 1 to n.
  • Print the root of the min-heap.
  • If the element is greater than the root of the min-heap, then pop the root and insert the element.

Example

Let's see the code.

 Live Demo

#include <bits/stdc++.h> using namespace std; void findKthSmallestElement(int elements[], int n, int k) {    priority_queue<int, vector<int>, greater<int>> queue;    for (int i= 0; i < k - 1; i++) {       queue.push(elements[i]);       cout << "- ";    }    queue.push(elements[k-1]);    for (int i = k; i < n; i++) {       cout << queue.top() << " ";       if (elements[i] > queue.top()) {          queue.pop();          queue.push(elements[i]);       }    }    cout << queue.top() << endl; } int main() {    int arr[] = {3, 5, 6, 2, 7, 8, 2, 3, 5, 9};    findKthSmallestElement(arr, 10, 5);    return 0; }

Output

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

- - - - 2 3 3 3 5 5

Conclusion

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