使用`std::greater`通过`priority_queue`创建最小堆的原因

Question

我想知道为什么要使用

priority_queue

创建最小堆，应该使用

std::greater

？

std::priority_queue<T, std::vector<T>, std::greater<T> > min_heap;

对我来说，由于最小值总是位于堆的顶部，所以使用的类应该是

std::less

更新： 另一方面，由于

priority_queue

（最大堆）的默认行为是将最大值保留在顶部，因此在我看来，

std::greater

应该用于最大堆创建，而不是用于最小堆创建

Answer 1

逻辑论证如下

```
std::priority_queue
```
是容器适配器；出于基本的内存考虑，背面成为对序列容器（例如
```
pop_back()
```
）进行修改（使用
```
push_back()
```
和
```
std::vector
```
）的首选位置。

priority_queue

原语基于

std::make_heap

（构造函数）、

std::pop_heap

+

container::pop_back

(

priority_queue::pop

) 和

container::push_back

+

std::push_heap

(

priority_queue::push

)

```
pop_heap
```
将获取底层存储的front，并将其放在back，然后恢复堆不变量。
```
push_heap
```
则相反。
在
```
sort_heap
```
上执行
```
max_heap
```
（最初最大值位于前面）将反复将前面弹出到后面并根据
```
less
```
（这是默认的比较运算符）对范围进行排序
因此，
```
max_heap
```
的首选实现是让最大元素w.r.t.
```
less
```
在前面，通过
```
priority_queue::top
```
（位于下面的
```
container::front
```
）访问。
人们仍然可以争论带有
```
priority_queue
```
比较器的
```
std::less
```
代表
```
max_heap
```
是否直观。它可以通过反转比较器的参数来定义为
```
min_heap
```
（但请参阅 @T.C. 的评论，对于 C++98 绑定器，这相当冗长）在对各种堆函数的调用中的任何地方。一个（对我来说）反直觉的结果是
```
top()
```
不会给予具有 top 优先级

Answer 2

C++ 堆函数

make_heap

、

push_heap

和

pop_heap

在 max 堆上运行，这意味着使用默认比较器时，顶部元素是 maximum。因此，要创建最小堆，您需要使用

greater<T>

而不是

less<T>

。

我怀疑使用最大堆而不是最小堆是因为用

less

操作更容易实现。在 C++ 中，

less

具有成为所有 STL 算法的“默认”比较器的特殊特权；如果您只想实现一项比较操作（

==

除外），则应该是

。这导致了一个不幸的怪癖，即

priority_queue<T, C<T>, less<T>>

表示最大队列，而

priority_queue<T, C<T>, greater<T>>

表示最小队列。

此外，某些算法（例如

nth_element

）需要最大堆。

Answer 3

这是一个将优先级队列转化为有序序列的过程。

我们怎样才能实现这一目标？

假设我们现在有一个最大堆，我们采取以下过程。

HEAP-SORT(A)
    for i = A.heap_size downto 2
        exchange A[1] with A[A.heap_size]
        A.heapsize -= 1
        max_heapify(A)

当我们完成这个过程时，我们得到一个递增的顺序序列。

我们注意到，每次比较两个元素时，我们总是将较大的元素放回数组，这意味着较小的元素位于较大元素的左侧。

这与我们将 less 运算符传递给 std::sort 算法以获得递增顺序序列时的想法相匹配。

Answer 4

A

priority_queue

是一种数据结构，其存储元素的方式是具有最高优先级的元素始终位于队列的顶部。默认情况下，元素的优先级由其值决定。但是，您可以使用函子来更改确定元素优先级的方式。

函子是一个小函数对象，可用于执行特定任务。在本例中，

greater<int>

函子用于比较两个整数，如果第一个整数大于第二个整数，则返回 true。

当您将

greater<int>

函子与

priority_queue

一起使用时，具有最低值的元素将被视为具有最高优先级。这是因为当将具有最低值的元素与任何其他元素进行比较时，

greater<int>

函子将始终返回 true。

Answer 5

来自 cppreference

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

Compare - 提供严格弱排序的比较类型。注意 Compare 参数的定义是，如果其满足以下条件，则返回 true：第一个参数以弱顺序出现在第二个参数之前。但由于优先级队列先输出最大的元素， “先于”的元素实际上是最后输出的。那就是队列的前面包含根据弱的“最后”元素由比较强加的排序。

使用`std::greater`通过`priority_queue`创建最小堆的原因

问题描述投票：0回答：5

5个回答

最新问题

使用`std::greater`通过`priority_queue`创建最小堆的原因

问题描述 投票：0回答：5

5个回答

最新问题

问题描述投票：0回答：5