# Heap 取出最小值

## **目標**

`std::priority_queue` 會從最大值開始 pop，但假如我希望可以從最小值拿 ... ？

## **方法**

### 反元素

假如臨時想不起來後面的做法也暫時沒有 Document 可以查(例如在打比賽？？)，然後元素又是可以取反元素的那種，那大概可以立刻想出這種臨時的方式：

* push 進去時先取反元素
    
* pop 出來後再做反元素
    

說不上甚麼好處，但是就很容易想到。

### `std::greater<T>`

首先， `std::priority_queue` 完整的 template 參數是：

```cpp
template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
```

第三個參數 Compare，預期要是一個 Functor ，假如兩個數值放進去比較後是 `true` ，那**第一個數**會比較晚從 queue 裡面拿出來。

`std::less(x, y)` 基本上是 `x < y` ，所以越小拿出的時候越晚。

所以在這裡只要改成 `std::greater` 就可以變成越小越快拿出來。 Example:

```cpp
std::priority_queue<int, std::vector<int>, std::greater<int>> pq3;
```

### `decltype([](int x, int y) { return x > y; })`

在 C++20 之後，可以對一個 lambda 取 decltype，假如我們寫

```cpp
std::priority_queue<int, std::vector<int>,
                    decltype([](int x, int y) { return x > y; })> pq4;
```

那就會是取得這個由 lambda 語法糖所生成的 struct (當然，應該不會這麼簡單)：

```cpp
struct __blabla__ {
    bool operator (int x, int y) const {
        return x > y;
    }
};
```

然後送去當 Compare

```cpp
std::priority_queue<int, std::vector<int>, __blabla__> pq4;
```

這樣和 `std::greater<int>` 有相同的效果。