Heap 取出最小值

目標

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

方法

反元素

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

• push 進去時先取反元素

• pop 出來後再做反元素

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

std::greater<T>

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

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:

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

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

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

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

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

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

然後送去當 Compare

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

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