# Max-heap O(N + Nlog(N) + Klog(N)) and Min-Heap O(N + (N-K)log(K) + KlogK) method

• ``````class Solution {
typedef pair<int, int> PAIR;
struct ComparisonClass {
bool operator() (const PAIR &lhs, const PAIR &rhs) {
return lhs.second < rhs.second;
};
};

struct ComparisonClassMin {
bool operator() (const PAIR &lhs, const PAIR &rhs) {
return lhs.second > rhs.second;
};
};
public:
vector<int> topKFrequent(vector<int>& nums, int k) {

map<int,int> hash;
for (int i = 0; i< nums.size(); ++i) {
if (hash.find(nums[i]) != hash.end()) {
hash[nums[i]]+=1;
} else {
hash[nums[i]] =1;
}
}
/* // This is Max heap method. Created Max heap of top number and extracted K items from the heap.
// Complexity is O(N + Nlog(N)). O(N) for creation of heap. O(Klog(N)) for extracting K elements from heap.
// Overall complexity O(N + Nlog(N) + O(Klog(N)))
priority_queue< PAIR, vector<PAIR>, ComparisonClass> pq(hash.begin(), hash.end());
vector<int> out;
for (int i = 0; i<k;++i) {
out.push_back(pq.top().first);
pq.pop();
}
return out;*/

// The Other method is min-heap method. ,Where we create Min-Heap for K elements
// For rest of the elements if root of heap is smaller than every further element. Remove root and insert the element.
// The remaining items in the heap are Top elements.
// O(K) for creating heap. O(N-K(logK)) for inserting remaining N-K elements. O(KLogK) for extracting all K elements
// Overall Complexity O(K + (N-K)log(K) + KlogK) this is significantly less than above method.

priority_queue< PAIR, vector<PAIR>, ComparisonClassMin> pq;

map<int,int>::iterator start = hash.begin();
map<int,int>::iterator end = hash.end();
int i = 0;
while(start != end) {
if (i < k) {
pq.push(make_pair(start->first,start->second));
} else {
if (pq.top().second < start->second) {
pq.pop();
pq.push(make_pair(start->first,start->second));
}
}
++i;
++start;
}
vector<int> out;
while(!pq.empty()) {
out.push_back(pq.top().first);
pq.pop();
}
reverse(out.begin(), out.end());
return out;
}
};
``````

Code along with explanation

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