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.