# Heap - Priority Queue Implementation, Question Patterns

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