# Heap (Priority Queue)

## Overview

A heap, or a priority queue, is a data structure that efficiently stores elements in a particular order. It is very efficient in inserting an element to the heap ($O(logN)$), and very efficient in removing the first element of the heap ($O(logN)$). To know the details of heap, we recommend you to look at this.

## Operations

### Insertion

To do insetion in heap, we would add the new element to the end of the heap. If the position of the new element violates the heap properity, the new elements will be sifted up until it reaches the correct position.

### Deletion

In heap, the deletion refers to pop the root in the heap. After the root of the heap has been popped out, the last element in the heap will be inserted to the root position. If this violates the heap porperity, the new root would be sifted down until it reaches the correct position.

## Python

By default, when we refer to heap, most implementations are min-heaps. This means the first element is always the smallest element.

In Python, you can use the following functions to interact with a heap:

`heap = [] #to initialize a heap, it is just a list`

heappush(heap, 3) # to add an element to the heap, we can use heappush

#heap = [3]

heappush(heap, 5)

#heap = [3, 5] , the heap always keeps the smallest element in front!

smallest_element_from_heap = heappop(heap) #we can remove the first element from heap with heappop

#heap = [5] , 3 is removed

#smallest_element_from_heap = 3 #after heappop, it is stored in the variable

That's it! These are the operations you need for using heap in LeetCode.

There is one more trick to learn for using heap. How do we tweak the heap to make it a max-heap?

`max_heap = []`

#we want to store 10, but change it to -10 for max-heap

heappush(max_heap, -10)

#max_heap = [-10]

#we want to store 7, but change it to -7 for max-heap

heappush(max_heap, -7)

#max_heap = [-10, -7]

max_element_from_heap = -1 * heappop(heap)

#heap = [-7], -10 is removed

#max_element_from_heap = 10, we have retrieved the largest element from the heap

Let's work on a problem (LeetCode Link)

You are given an array of integers

`stones`

where`stones[i]`

is the weight of the`ith`

stone.We are playing a game with the stones. On each turn, we choose the

heaviest two stonesand smash them together. Suppose the heaviest two stones have weights`x`

and`y`

with`x <= y`

. The result of this smash is:

- If
`x == y`

, both stones are destroyed, and- If
`x != y`

, the stone of weight`x`

is destroyed, and the stone of weight`y`

has new weight`y - x`

.At the end of the game, there is

at most onestone left.Return

the smallest possible weight of the left stone. If there are no stones left, return`0`

.

I want you to think about these questions before working on it:

- Should we use a min-heap or a max-heap?
- If it is a max-heap, how to we "store" the numbers?
- What do we have to check before retrieving the two heaviest stones?

As we need to get the two heaviest stones in every iteration, we should use a max-heap for quick access of the largest elements. To use a max-heap, we can store the negative of the integer. We have to check if there are at least two more stones in the heap before retrieving the two heaviest stones.

`def lastStoneWeight(self, stones: List[int]) -> int:`

#initialize the max_heap

max_heap = []

#add elements to max_heap

for stone in stones:

#store its negative to keep the most positive stone in front

heappush(max_heap, -stone)

#we have to check if there are at least two stones in the heap

while(len(max_heap) > 1):

#pop the largest element from max_heap, multiplied by -1

largest_stone = -1 * heappop(max_heap)

#pop the second largest element (now largest) from max_heap, multiplied by -1

second_largest_stone = -1 * heappop(max_heap)

#push the new stone if they are not equal

if(largest_stone != second_largest_stone):

new_stone = largest_stone - second_largest_stone

#remember to store its negative

heappush(max_heap, -new_stone)

#if there is a stone left, return the stone, its positive value

if(max_heap):

return -max_heap[0]

#if no stone left, return 0

return 0

## C++

In C++, when we are refer to heap, we mostly refer to priority queue. By default, priority queue is a max heap in c++.

Create a max heap:

`priority_queue<int> max_heap; // max heap `

Create a min heap:

`priority_queue<int,vector<int>,greater<int>> min_heap; // min heap `

Other related function:

`priority_queue<int> max_heap; //max heap`

//To push element into a priority queue

max_heap.push(1);

max_heap.push(2);

max_heap.push(3);

//max_heap now contains: {3,2,1}

//To push element from a vector into a priority queue

vector<int> vc = {6,5,4};

for (auto x:vc){

max_heap.push(x);

}

//max_heap now contains: {6,5,4,3,2,1}

//To get element from the priority queue

int top_element = max_heap.top();max_heap.pop();

cout<<top_element; //output: 6

//As we want to access the second largest element later, we need to remove the max element after we access it.

//To get all element from the priority queue

while(!max_heap.empty()){

int element = max_heap.top();max_heap.pop();

cout<<element<<" "; //output: 5 4 3 2 1

}

**Advance usage:** Use heap to sort the element by value while containing the index of the elements.

Let's work on a problem (LeetCode Link)

you are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of >the civilians. That is, all the 1's will appear to the left of all the 0's in each row.

A row i is weaker than a row j if one of the following is true:

The number of soldiers in row i is less than the number of soldiers in row j. Both rows have the same number of soldiers and i < j. Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

The idea of this question is

- count the number of soilders in each row
- sort it
- return the 1st - kth weakest
**index**of row

We will use a min heap as we want the result rank from `weakest to strongest`

.

Create a min heap which will contains `pair of {number of soldiers in the row, row index}`

. By default, c++ will rank the order of element by the first element in the heap. In this case, it will be `number of soldiers`

`priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;`

//priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq; // this line will also work

To access the `pair of {number of soldiers in the row, row index}`

`pair<int,int> top_element;`

top_element=pq.top();pq.pop();

int number_of_soldiers = top_element.first;

int index = top_element.second;

My solution:

`vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {`

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<>> pq; //min heap

//push elements to min heap

for (int i =0;i<mat.size();i++){

int count= 0;

for (int j=0;j<mat[0].size();j++){

if (mat[i][j] == 1) count++;

}

pq.push({count,i}); //push pair of {number of soldiers in the row, row index} to the min heap

//pq.push(make_pair(count,i)); can replace with this line of syntax

}

vector<int> result;

int count = 0;

//get the index only from the heap and put it in the array

while(!pq.empty() && count<k){

count++;

int ans = pq.top().second;

pq.pop();

result.push_back(ans);

}

return result;

}

**Additional knowledge:** You can create a `max heap with pair<int,int>`

with following syntax

`priority_queue<pair<int,int>> pq;`

### Suggested Problems

Problem Name | Difficulty | Solution Link |
---|---|---|

0703 - Kth Largest Element in a Stream | Easy | View Solutions |

0215 - Kth Largest Element in an Array | Medium | View Solutions |

0973 - K Closest Points to Origin | Medium | View Solutions |