# C++ solution with priority queue

• I first use a hash map to collect the frequency, then build a priority queue in descending order based on frequency. Then final output is easy to reconstruct.

``````class wordWithFreq {
public:
char val;
int freq;
wordWithFreq(char c, int k)
{
val = c;
freq = k;
}
};

class wordWithFreq_compare {
public:
bool operator() (wordWithFreq& w1, wordWithFreq& w2) {
return w1.freq < w2.freq;
}
};

class Solution {
public:
string frequencySort(string s) {
if(s.length() == 0) return s;
// Step 1: get the frequency
unordered_map<char, int> myMap;
for(auto ss : s)
myMap[ss] ++;

// Step 2: build up the priority queue
priority_queue<wordWithFreq,vector<wordWithFreq>,wordWithFreq_compare> myQueue;
for(auto item : myMap)
{
wordWithFreq* t = new wordWithFreq(item.first, item.second);
myQueue.push(*t);
}

// Step 3; reconstruct the string
s.clear();
while(!myQueue.empty())
{
wordWithFreq item = myQueue.top();
myQueue.pop();
for(int i = 0; i < item.freq; i ++)
s += item.val;
}
return s;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.