Prerequisites :
What are Priority Queues
In C++ Standard template library, we have priority_queue which can be directly used to implement binary heap. This saves us the time and effort of implementing a heap from scratch. However, it is good to know both of these ways.
A priority_queue is very similar to a stack, it has the following major operations :
push: Inserts the element in max/min-heap.pop: Extracts the root of the max/min-heap.top: Returns the value of the root of max/min-heap.
We need not worry about heapifying or looking after the violating operations. priority_queue takes care of it. It always keeps the root of the heap on the top, even after you push or pop an element.
Syntax for creating Max Heap of integers :
priority_queue<int> maxHeap;
Syntax for creating Min Heap of integers :
priority_queue<int, vector<int>, greater<int>> minHeap;
If using a user-defined type, greater<int> can be replaced by a comparator function that takes 2 arguments and returns a bool value.
Creating a max heap :
int main()
{
// defining max heap
priority_queue <int> pq;
// insert nodes in the heap
/*the greatest number will always be at the top of the priority_queue, denoting the root of max heap*/
pq.push(2); // pq.top() = 2
pq.push(4); // pq.top() = 4
pq.push(7); // pq.top() = 7
pq.push(1); // pq.top() = 7
pq.push(9); // pq.top() = 9
// Extracting elements from max-heap
while(pq.empty()==false)
{
cout<<pq.top()<<" ";
pq.pop();
}
}
Explanation :
Output :
9 7 4 2 1
Creating a min-heap :
int main ()
{
// defining min heap
priority_queue <int, vector<int>, greater<int> > pq;
// insert nodes in the heap
/*the smallest number will always be at the top of the priority_queue, denoting the
root of min heap*/
pq.push(2); // pq.top() = 2
pq.push(4); // pq.top() = 2
pq.push(7); // pq.top() = 2
pq.push(1); // pq.top() = 1
pq.push(9); // pq.top() = 1
// One by one extract items from min heap
while (pq.empty() == false)
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
Explanation :
Output:
1 2 4 7 9
Question Patterns
Most of the questions related to heap are of the pattern Top K elements.
They can be of following variations
- Top K smallest/largest numbers.
- Top K frequent numbers.
- Frequency Sort.
- Top K closest numbers etc.
Now, let us understand how can we solve such questions using a heap.
Consider a max heap, if you insert N elements in it, the time complexity is O(N*log N).
But if you insert K elements in the heap, the time complexity becomes O(N*log K).
Question: Find Top 3 largest numbers in the given array
Consider the array as [1, 5, 6, 9, 2, 3, 10]
Brute-force method :
- Sort the array and then traverse =>
O(n*log n)
Solution using heap:
- Let us insert all these elements in the min-heap.
Inserting all these elements took O(n*log n) time.
But what if we create a heap of size=k.
- We first insert the first k elements in the array =>
O(k*log k) - We check for each of the rest n-k elements, if the element is greater than the top of the heap, pop the top element from the heap, and insert the current element =>
O((n-k)*log k)
And O(k*log k) + O((n-k)*log k) = O(n * log k) and this is much better than O(n*log n).
void findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
// Push k elements in the heap
for(int i=0;i<k;i++)
{
pq.push(nums[i]);
}
// Check for each of the n-k elements
for(int i=k;i<nums.size();i++){
if(nums[i]>pq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
cout<<" The top k elements are :"<<endl;
while(!pq.empty()){
cout<<pq.top()<<" ";
pq.pop();
}
}
Hence, we can conclude for further similar questions :
This could be understood by the following image :
Please leave your feedback and suggestions :)
References