# Priority Queue

By default:

* `priority_queue` is a **Max-heap**. The element with the highest priority is at the top.
* `priority_queue` uses `less` as comparator. (In fact, STL always use `less` as the default comparator whenever it needs comparison.)

If you want to get a Min-heap, use `priority_queue<int, vector<int>, greater<int>>`.

It uses `make_heap`, `push_heap` and `pop_heap` algorithm functions under the hood.

## Why is it Max-heap by default?

> The elements are compared using operator`<` (by default), or `comp` (custom comparator): The element with the highest value is an element for which this would return `false` when compared to every other element in the range.

<http://www.cplusplus.com/reference/algorithm/make_heap>

In priority queue, the element with the highest priority is the one which gets `false` when comparing with every other element using the comparator. The comparator is by default `less`. So the element that is not less than any other elements, i.e. the largest one, is at the top.

```
           front                           back 
             v                               v
vector: [   10,              ...             2  ]
             ^
          heap top
```

After poping the top

```
           front                        back     popped element
             v                           v              v
vector: [    8,              ...         2  ]        [ 10 ]
             ^
          heap top
```

## Related functions

Note: try to solve [215. Kth Largest Element in an Array (Medium)](https://leetcode.com/problems/kth-largest-element-in-an-array/) using the following functions.

### `make_heap`

Rearranges the elements in the range `[first,last)` in such a way that they form a *heap*.

The element with the highest value is always pointed by *first*.

```cpp
// range heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
    int myints[] = {10,20,30,5,15};
    std::vector<int> v(myints,myints+5);

    std::make_heap (v.begin(),v.end());
    std::cout << "initial max heap   : " << v.front() << '\n';

    std::pop_heap (v.begin(),v.end()); v.pop_back();
    std::cout << "max heap after pop : " << v.front() << '\n';

    v.push_back(99); std::push_heap (v.begin(),v.end());
    std::cout << "max heap after push: " << v.front() << '\n';

    std::sort_heap (v.begin(),v.end());

    std::cout << "final sorted range :";
    for (unsigned i=0; i<v.size(); i++)
        std::cout << ' ' << v[i];

    std::cout << '\n';

    return 0;
}
```

Output:

```
initial max heap   : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99
```

### `push_heap`

Given a heap in the range `[first,last-1)`, this function extends the range considered a heap to `[first,last)` by placing the value in `(last-1)` into its corresponding location within it.

### `pop_heap`

Rearranges the elements in the heap range `[first,last)` in such a way that the part considered a heap is shortened by one: The element with the highest value is moved to `(last-1)`.

### `sort_heap`

Sorts the elements in the heap range `[first,last)` into ascending order.

The range loses its properties as a heap.

## Custom Comparator

```cpp
// Assume there is a `m` variable in the context and `m[a]` is the frequency of `a`
// In following code, the element with the highest frequency is the root.
auto cmp = [&](int a, int b) { return m[a] < m[b]; };
priority_queue<int, vector<int>, decltype(cmp)> q(cmp);
```

Another way

```cpp
class Cmp {
public:
    bool operator() (const pair<int, int>& a, const pair<int, int>& b) const {
        return a.second < b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> q(m.begin(), m.end()); // Assume there is an `m` storing pairs of `value, frequency`.
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://liuzhenglaichn.gitbook.io/algorithm/stl/priority_queue.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.