Heap: Given an array, sort the array using min heap

Problem Statement:

You are given a array, sort the array in decreasing order using min heap

Example:

Input: arr[] = {5, 4, 3, 6, 1, 2}
Output: arr[] = {6, 5, 4, 3, 2, 1}

Solution Explanation: Using inbuilt priority queue

Insert the elements of the array into PQ.

Then copy the elements from PQ to array to return the result.

Time Complexity: O(logn)
Space Complexity: O(n)

Code Solution

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<int>& arr) 
{
    priority_queue<int, vector<int>, greater<int> > pq;

    for (int num : arr) {
        pq.push(num);
    }

    vector<int> result;

    while (!pq.empty()) 
    {
        int top = pq.top();
        pq.pop();
        result.insert(result.begin(), top);
    }

    return result;
}

int main()
{
    vector<int> arr = { 5, 4, 3, 6, 1, 2 };
    vector<int> result = solution(arr);

    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

Output

6 5 4 3 2 1