/**
* @param {string} s
* @return {string}
*/
var frequencySort = function (s) {
const map = {}
for (let i = 0; i < s.length; i++) {
const c = s[i];
map[c] = (map[c] || 0) + 1
}
// 堆的数据结构 [char, count]
const list = Object.keys(map).map(c => [c, map[c]])
const heap = new MaxHeap(list, function comparator(inserted, compared) {
return inserted[1] < compared[1];
});
let str = ''
while (heap.size() > 0) {
const [char, cnt] = heap.pop();
str += char.repeat(cnt)
}
return str
};
// **************************************************
class Heap {
constructor(list = [], comparator) {
this.list = list;
this.comparator = comparator;
this.init();
}
init() {
const size = this.size();
for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
this.heapify(this.list, size, i);
}
}
insert(n) {
this.list.push(n);
const size = this.size();
for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
this.heapify(this.list, size, i);
}
}
peek() {
return this.list[0];
}
pop() {
const last = this.list.pop();
if (this.size() === 0) return last;
const returnItem = this.list[0];
this.list[0] = last;
this.heapify(this.list, this.size(), 0);
return returnItem;
}
size() {
return this.list.length;
}
}
class MaxHeap extends Heap {
constructor(list, comparator) {
super(list, comparator);
}
heapify(arr, size, i) {
let largest = i;
const left = Math.floor(i * 2 + 1);
const right = Math.floor(i * 2 + 2);
if (left < size && this.comparator(arr[largest], arr[left]))
largest = left;
if (right < size && this.comparator(arr[largest], arr[right]))
largest = right;
if (largest !== i) {
[arr[largest], arr[i]] = [arr[i], arr[largest]];
this.heapify(arr, size, largest);
}
}
}