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

Question

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

39

我想知道为什么在使用priority_queue创建最小堆时，应该使用std::greater？

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

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

更新： 另一方面，由于priority_queue（最大堆）的默认行为是将最大值保持在顶部，因此看起来应该使用std::greater来创建最大堆而不是最小堆。

- Vahid Noormofidi

1

你在看哪里？我现在正在阅读cppreference.com，他们指定std::less为默认值，并说替换为std::greater会导致最小的元素出现在“顶部”，而不是最大的元素。这似乎只是一种惯例，对吧？ - sunny

5

我认为这是一个非常好的问题。我发现很奇怪的是，很少有人质疑这个特定的设计决策。到目前为止，你和我一样，似乎是唯一一个觉得这种“反向”比较器使用非常不直观的人。我不会质疑这个决策背后的性能原因，但对我来说它并不自然。 - user1593842

1

我在回答另一个问题时遇到了这个问题，当你编写自己的比较器时，它会感觉特别不自然。 - EnigmaticBacon

有点奇怪。heapify_down是：如果更大，则将其向下移动。而heapify_up则是：如果不更大，则将其向上移动。 - Paschalis

4个回答

8

C++堆函数make_heap、push_heap和pop_heap操作的是最大堆，这意味着使用默认比较器时，顶部元素是最大值。因此，要创建一个最小堆，你需要使用greater<T>而不是less<T>。

我怀疑为什么使用最大堆而不是最小堆，是因为使用less操作更容易实现。在C++中，less具有特殊特权，它是所有STL算法的“默认”比较器；如果你只实现一个比较操作（除了==），那应该是<。这导致一个不幸的怪癖，即priority_queue<T, C<T>, less<T>>表示最大队列，而priority_queue<T, C<T>, greater<T>>表示最小队列。

另外，某些算法如nth_element需要一个最大堆。

- rlbond

1

这并没有回答为什么使用 less 会导致最大堆，而 greater 则会导致最小堆的问题。 - Sebastian Redl

1

那么，让我看看我是否正确地理解了你的意思。你的意思是因为“less”是默认比较器，而“max_heap”更有用，所以我们最终需要通过“less”而不是“greater”来实现“max_heap”？ - Vahid Noormofidi

我认为使用less实现最小堆和使用max-heap实现最大堆并没有什么区别。然而，如果你想要与std::sort相同的排序顺序，并使用相同的比较运算符，那么从最大堆中实现std::sort_heap肯定更容易（也更有效率）。这个事实可能有助于推理过程。 - Benjamin Lindley

2

@TemplateRex: 因为当你从堆中弹出一个元素时，你会留下末尾的一个空间，你可以在那里放置你刚刚弹出的元素（即最大的元素）。为了得到正确的顺序，如果你从一个最小堆开始，你需要在完成后反转范围。 - Benjamin Lindley

@BenjaminLindley 将这个评论对话总结成了一个新的答案。 - TemplateRex

显示剩余2条评论

1

这是一个将优先队列转换为排序序列的过程。

我们如何实现呢？

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

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算法以获得递增顺序序列的想法相匹配。

- Wang

0

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

函数对象是一个小型函数对象，可用于执行特定任务。在这种情况下，greater<int> 函数对象用于比较两个整数，并在第一个整数大于第二个整数时返回 true。

当您将 greater<int> 函数对象与 priority_queue 一起使用时，具有最低值的元素将被视为具有最高优先级。这是因为当比较具有最低值的元素与任何其他元素时，greater<int> 函数对象将始终返回 true。

- ADI

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- TemplateRex · Accepted Answer

逻辑论证如下。

std::priority_queue是一个容器适配器；对于诸如std::vector等序列容器，基本的内存考虑使得后端成为修改的首选位置（使用pop_back()和push_back())。
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将会取出底层存储的前端并将其放置在后端，然后恢复堆不变式。push_heap则相反。
在max_heap上执行sort_heap（初始时最大值在前面）将反复将前端元素移到后面并根据默认比较运算符less对范围进行排序。
因此，实现max_heap的首选方法是将相对于less具有最大值的元素放在前面，并通过priority_queue::top（底层container::front）访问。
人们仍然可以争论使用std::less比较器的priority_queue是否直观地表示了一个max_heap。通过在调用各种堆函数时反转比较器的参数（但请参见@T.C.的评论，使用C++98绑定器会非常冗长），可以将其定义为min_heap。对我来说，唯一不直观的结果是top()将无法给出具有最高优先级的元素。