  # Heap - Priority Queue Implementation, Question Patterns

Subscribe to my newsletter and never miss my upcoming articles

Prerequisites :

Heaps Introduction

### 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 :

1. `push`: Inserts the element in max/min-heap.
2. `pop`: Extracts the root of the max/min-heap.
3. `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 : References

geeksforgeeks.org/implement-min-heap-using-..

educative.io/edpresso/find-the-kth-smallest..