有人可以告诉我 STL 堆函数模板的意义std::make_heap吗？为什么有人会使用它们？有实际用途吗？
问问题
26611 次
7 回答
48
您的直接问题将由算法和数据结构方面的课程很好地回答。在计算机科学的算法中，堆被广泛使用。引用下面链接的 make_heap 函数，“堆是一棵树，其中每个节点都链接到不大于其自身值的值。” 虽然堆有很多应用程序，但我最常使用的应用程序是当您想要有效地跟踪 N 值的排序列表时的搜索问题。
当我第一次遇到 STL 堆函数时，我和你有类似的困惑。我的问题有点不同。我想知道“为什么 STL 堆与 std::vector 不在同一类数据结构中？” 我认为它应该像这样工作：
std::heap< int > my_heap;
my_heap.heap_insert( 7 );
my_heap.heap_insert( 3 );
STL 堆函数背后的想法是，它们允许您从几个不同的底层 STL 容器（包括 std::vector）中创建堆数据结构。如果您想传递容器以在程序的其他地方使用，这将非常有用。它也有点好，因为如果你选择使用 std::vector 以外的东西，你可以选择堆的底层容器。您真正需要的是以下内容：
template <class RandomAccessIterator>
void make_heap ( RandomAccessIterator first, RandomAccessIterator last );
这意味着您可以将许多不同的容器放入堆中。比较器在方法签名中也是可选的，您可以阅读更多有关可以在 STL 页面中为 make_heap 函数尝试的不同内容的信息。
链接：
于 2009-06-03T22:17:13.313 回答
21
如果你想从列表中创建一个优先级队列，那么你可以使用 make_heap：
在内部，堆是一棵树，其中每个节点都链接到不大于其自身值的值。在 make_heap 生成的堆中，一个元素在树中的具体位置，而不是由消耗内存的链接确定，是由它在序列中的绝对位置确定的，*first 始终是堆中的最大值。
堆允许使用函数 push_heap 和 pop_heap 以对数时间从其中添加或删除元素，这些函数保留其堆属性。
于 2009-06-03T21:41:52.087 回答
9
您应该与向量或数组std::make_heap()一起使用std::push_heap()并std::pop_heap()维护二进制堆；后两个函数保持堆不变。你也可以使用std::heap_sort()这样的堆来排序。虽然您确实可以将其std::priority_queue用于优先级队列，但它不会让您了解它的内部，而这可能是您想要做的。此外，std::make_heap()并std::heap_sort()一起制作了一种非常简单的在 C++ 中进行堆排序的方法。
于 2009-06-04T06:21:24.067 回答
8
std::make_heap几乎不应该在实践中使用。虽然堆确实对优先级队列很有用，但这并不能解释为什么要手动维护结构。std::priority_queue如果您只需要一个优先级队列，则它具有更有用的界面。
如果您make_heap直接使用及其同级，则必须确保每次更改底层容器时都使用它们。我见过他们使用了两三次，而且每次都被错误地使用。
我自己只直接使用过一次堆操作，因为我需要使用一段时间作为优先级队列，然后对其进行排序。您很可能永远不需要std::make_heap.
如果您需要一个能够更改元素的优先级队列，您可以使用std::set. *s.begin()您可以使用or分别获取最小或最大元素，*s.rbegin()并通过删除旧值并插入新值来更新元素。
于 2011-04-09T13:52:06.700 回答
7
基本上有两种方法可以构建[二进制]堆：创建一个空堆并将每个元素一次插入其中，或者获取一系列值并将它们堆起来。
堆上的每个推送操作都需要 O(logn) 时间，因此如果将 N 个项目推送到堆上，则需要 O(NlogN) 时间。然而，从一个值数组构建一个二进制堆只需要 O(N) 时间。
因此，将每个元素插入数组（或其他支持随机访问迭代器的容器）然后在数组上调用 make_heap() 比在插入时维护堆结构更有意义。
于 2009-06-04T20:56:22.867 回答
4
除了上述之外，STL 的排序算法是introsort，它是快速排序和堆排序的混合体（如果前者表现不佳，它会从快速排序故障转移到堆排序）。make_heap 创建一个堆结构，这是运行 heapsort 所需要的，这是 introsort 所需要的。
于 2009-06-03T21:50:24.490 回答
2
它们用于构建和维护堆数据结构
于 2009-06-03T21:41:33.227 回答