# 85% Heap and hashmap solution, without using set or map

• I admit it's not n*logk, but it's much faster than black red tree, even when compiling with -O0

``````template <typename K, typename V>
class priority_hashmap {
public:
unordered_map<K, int> ktol;
typedef pair<K,V> KV;
vector<KV> que;
function<bool(KV const&, KV const&)> comp;
priority_hashmap(function<bool(KV const&, KV const&)> &&comp):comp(comp) {
que.push_back(KV());
};
priority_hashmap(function<bool(KV const&, KV const&)> const& comp):comp(comp) {
que.push_back(KV());
};

V getv(K const& k) {
if (ktol.find(k) == ktol.end()) return V();
return que[ktol[k]].second;
}

void update(K const& k, V const& v) {
if (ktol.find(k) == ktol.end()) {
ktol[k] = que.size();
que.push_back({k,v});
} else {
que[ktol[k]].second = move(v);
}

}

void del(K const& k) {
int l = ktol[k];
qswap(l, que.size()-1);
K const& backk = que.back().first;
ktol.erase(backk);
que.pop_back();
if (l < que.size())
}

void pop(KV &kv) {
if (que.size() == 1) return;
kv = que[1];
qswap(1, que.size()-1);
del(kv.first);
}

V const& top() const {
return que[1];
}

private:

int nl = l;
while (nl > 1) {
int pl = (nl>>1);
if (comp(que[nl], que[pl])) {
qswap(nl, pl);
nl = pl;
} else {
break;
}
}

if (nl < l) return;
nl = (l<<1);
while (nl < que.size()) {
int s = l;
if (comp(que[nl], que[s])) s = nl;
if (nl+1 < que.size() && comp(que[nl+1], que[s])) s = nl+1;
if (l != s) {
qswap(l, s);
l = s; nl = (l<<1);
} else break;
}
}

void qswap(int a, int b) {
if (a == b) return;
K const& ka = que[a].first;
K const& kb = que[b].first;
swap(ktol[ka], ktol[kb]);
swap(que[a], que[b]);
}
};
class Solution {
public:

vector<string> topKFrequent(vector<string>& words, int k) {
typedef pair<string, int> KV;
priority_hashmap<string, int> pm([](KV const& a, KV const& b)->bool{
if (a.second == b.second) return a.first < b.first;
return a.second > b.second;
});
vector<string> ret;
unordered_map<string, int> dcnt;
for (auto &w : words) {
dcnt[w]++;
}
for (auto &kv : dcnt) {
pm.update(kv.first, kv.second);
}

KV tmp;
for (int i = 0; i < k; i++) {
pm.pop(tmp);
ret.push_back(tmp.first);
}
return ret;
}
};
``````

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