# K Most occurring elements-heap

Given a non-empty array of repeating integers return the *k* most frequent elements.

Example 1:

```
Input:
N = 8
arr[] = {3,1,4,4,5,2,6,1}
K = 2
Output: 4
Explanation: Since, 4 and 1 are 2 most
occurring elements in the array with
their frequencies as 2, 2. So total
frequency is 2 + 2 = 4.
```

### method 1:

**Algorithm:**

1)save all the array elements and its corresponding frequencies in a unordered map

2)create a vector and push only the frequencies of the elements in the vector

3)sort the vector

4)Run a loop k times, and in each iteration remove the largest element from the end of the vector and add them

**int kMostFrequent(int arr[], int n, int k)
{
unordered_map<int,int> mp; //create a unordered map
for(int i=0;i<n;i++)
mp[arr[i]]++; // save all the array elements and its corresponding frequencies in map
vector<int> v; //create a vector
for(auto u: mp){ //push only the frequencies in vector
v.push_back(u.second);
}
sort(v.begin(), v.end()); //sort the vector
int sum = 0;
while(k--){ // remove the k number of largest elements from the end of the vector
sum += v.back(); // and add them
v.pop_back();
}
return sum;
} **

**Time Complexity:**O(d log d), where**d**is the count of distinct elements in the array. To sort the array O(d log d) time is needed.**Auxiliary Space:**O(d), where**d**is the count of distinct elements in the array. To store the elements in Map O(d) space complexity is needed.

method 2:

similar to method one but instead of sorting we will use max heap(priority queue) in which largest element is always stored in root

Store the frequency in a Priority Queue and create the Priority Queue, this takes O(n) time

Run a loop k times, and in each iteration remove the top of the priority queue and print the element.

**int kMostFrequent(int arr[], int n, int k)
{
**
**unordered_map<int,int> mp; //create a unordered map
for(int i=0;i<n;i++)
mp[arr[i]]++; // save all the array elements and its corresponding frequencies in map
priority_queue <int>pq ; //create a max heap
for(auto u: mp){ //push only the frequencies in heap
pq.push(u.second);
}
int sum = 0;
while(k--){ // remove the k number of largest elements from the heap
sum += pq.top(); // and add them
pq.pop();
}
return sum;
} **

**Complexity Analysis:**

**Time Complexity:**O(k log d + d), where**d**is the count of distinct elements in the array.

To remove the top of priority queue O(log d) time is required, so if k elements are removed then O(k log d) time is required and to traverse the distinct elements O(d) time is required.**Auxiliary Space:**O(d), where**d**is the count of distinct elements in the array.

To store the elements in HashMap O(d) space complexity is needed.