# C++ Unordered Map with Heap Sort k elements

• ``````class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
if (nums.empty()) return vector<int>();

unordered_map<int, int> map;
for (int i=0; i < nums.size(); i++){
map[nums[i]]++; //time appear of a number
}

vector<pair<int, int>> bucket;

for ( auto it = map.begin(); it != map.end(); ++it ){
bucket.push_back(make_pair(it->second, it->first));   //bucket contains all pairs of (frequency - number)
}

//get the last k sorted in the list
//sort the first k element with Heap Algo
kth_element_sorted(bucket, k);

vector<int> result;

for (int i=0; i < k; i++){
result.push_back(bucket[bucket.size()-1-i].second);
}

return result;
}

//Heap sort implementing...
int left(int idx){
return (idx << 1) + 1;
}
int right(int idx){
return (idx << 1) + 2;
}
//maintain heap struct
void max_heapify(vector<pair<int, int>>& bucket, int idx){
int l = left(idx);
int r = right(idx);
int largest = idx;
if (l < heap_size && bucket[l].first > bucket[largest].first) largest = l;
if (r < heap_size && bucket[r].first > bucket[largest].first) largest = r;
if (largest != idx){
swap(bucket[largest], bucket[idx]);
max_heapify(bucket, largest);
}
}
//construct heap
void construct_max_heap(vector<pair<int, int>>& bucket){
heap_size = bucket.size();
for (int i=heap_size<<1-1; i >= 0; i--) {
max_heapify(bucket, i);
}
}

//reorganize k element
void kth_element_sorted(vector<pair<int, int>>& bucket, int k){
construct_max_heap(bucket);
for (int i=0; i < k; i++) {
swap(bucket[heap_size-1], bucket[0]);
heap_size--;
max_heapify(bucket, 0);
}
}
private:
int heap_size;
};
``````

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