451、根据字符出现频率排序（哈希 加优先队列）

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

示例 1:

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:

输入:
"cccaaa"

输出:
"cccaaa"

解释:
'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:

输入:
"Aabb"

输出:
"bbAa"

解释:
此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意'A'和'a'被认为是两种不同的字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-characters-by-frequency
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;
//优先队列 大顶堆实现 90% 
class Solution {
public:
    struct Cell
    {
        char c;
        int frequency;
        Cell(char ch, int freq):c(ch), frequency(freq) {};
        friend bool operator <(Cell c1, Cell c2)
        {
            if (c1.frequency == c2.frequency)
                return c1.c > c2.c;
            else
                return c1.frequency < c2.frequency;
        }
    };
    string frequencySort(string s) {
        map<char, int> hash;
        priority_queue<Cell> que;
        int len = s.length();
        for (int i = 0; i < len; i++)
            hash[s[i]]++;
        for (auto item : hash)
            que.push({ item.first, item.second });
        string res = "";
        while (!que.empty())
        {
            auto p = que.top();
            que.pop();
            for (int i = 0; i < p.frequency; i++)
                res += p.c;
        }
        return res;
    }
};
int main()
{
    string s;
    cin >> s;
    cout << Solution().frequencySort(s);
    return 0;
}