c++ - make_heap 的意义何在？

Question

有人能告诉我像 std::make_heap 这样的 STL 堆函数模板的意义吗？为什么有人会使用它们？有实际用途吗？

Answer 1

算法和数据结构方面的类(class)会很好地回答您的直接问题。在计算机科学的算法中，堆被广泛使用。引用下面链接的 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 函数尝试的不同内容。

链接:

• Heap Data Structure
• make_heap function