Heap: Frequency sort

Problem Statement:

You are given an array with repeated elements.
You need to sort such that the one that has ore frequency should come first.

Example

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

Solution

The solution is similar to previous question.
Convert the array into map, for element and corresponding frequency.

1 -> 3
2 -> 2
3 -> 1
4 -> 1

Now we need to sort based on frequency.
We need more frequency on the top, so we need to use max_heap.

Now push the pair and sort based on frequency.

Pass 1: 1 -> 3

Heap {1, 3}

Pass 2: 2 -> 2

Heap {1, 3} {2, 2}

Pass 3: 3 -> 1

Heap {1, 3} {2, 2} {3, 1}

Pass 4: 4 -> 1

Heap {1, 3} {2, 2} {3, 1} {4, 1}

Now pop the elements.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <unordered_map> 
#include <queue> 

using namespace std;


vector<int> frequency_sort(vector<int> v) 
{
  //to store the frequency of elements
  unordered_map<int, int> mp;
  for (int i = 0; i < v.size(); i++) 
  {
    mp[v[i]] ++;
  }

  //max_heap
  priority_queue <pair<int, int>> max_heap;

  //push the elements into max heap
  for (auto i = mp.begin(); i != mp.end(); i++) 
  {
    max_heap.push({i->second, i->first});
  }

  //store the result
  vector<int> result;

  while (!max_heap.empty()) 
  {
    int times = max_heap.top().first;

    for (int j = 0; j < times; j++) {
      result.push_back(max_heap.top().second);
    }

    max_heap.pop();
  }
  return result;
}

int main()
{
    vector<int> vec = { 1,1,1,3,2,2,4 };
 
    vector<int> res = frequency_sort(vec);

    cout<<"Result = ";

    for(int i = 0; i<res.size(); i++)
    {
      cout <<res[i]<< " ";
    }
    cout<<endl;
 
    return 0;
}

Output:

Result = 1 1 1 2 2 4 3