rlb*_*ond 46 c++ stl language-design
有人可以告诉我STL堆函数模板的重点std::make_heap吗？为什么有人会使用它们？有实际用途吗？
Jam*_*son 43
算法和数据结构中的类将很好地回答您的直接问题.堆在计算机科学中的算法中被广泛使用.要引用下面链接的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 );
这意味着您可以将许多不同的容器放入堆中.比较器在方法签名中也是可选的,您可以阅读有关make_heap函数的STL页面中可以尝试的不同内容的更多信息.
链接:
aka*_*ppa 21
如果要从列表中创建优先级队列,那么可以使用make_heap:
在内部,堆是树,其中每个节点链接到不大于其自身值的值.在由make_heap生成的堆中,元素在树中的特定位置而不是由消耗内存的链接确定由其在序列中的绝对位置确定,其中*first始终是堆中的最高值.
堆允许通过使用函数push_heap和pop_heap在对数时间内添加或删除元素,这些函数保留其堆属性.
您应该std::make_heap()与向量或数组一起使用std::push_heap()并std::pop_heap()维护二进制堆; 后两个函数保持堆不变.您还可以使用它std::heap_sort()来对这样的堆进行排序.虽然您可以使用std::priority_queue优先级队列,但它不会让您了解它的内部,这可能是您想要做的.此外,std::make_heap()和std::heap_sort()共同使用C做堆排序++的一个非常简单的方法.
std::make_heap应该几乎不会在实践中使用.虽然堆对优先级队列很有用,但这并不能解释为什么要手动维护结构.std::priority_queue如果你需要的只是一个优先级队列,它有一个更有用的接口.
如果您make_heap直接使用它的兄弟姐妹,则必须确保每次更改底层容器时都使用它们.我看过他们使用了两三次,而且每次使用都不正确.
我自己一直只使用堆操作,因为我需要使用一个向量作为优先级队列一段时间然后对它进行排序.你很可能永远不需要std::make_heap.
如果您需要具有更改元素功能的优先级队列,则可以使用std::set.您可以使用*s.begin()或*s.rbegin()分别获取最小或最大元素,并通过删除旧值并插入新值来更新元素.
构造[二进制]堆基本上有两种方法:创建一个空堆并一次一个地插入每个元素,或者获取一系列值并将它们堆积起来.
堆上的每个推送操作都需要O(logn)时间,因此如果要将N个项目推送到堆上,则需要O(NlogN)时间.但是,从值数组构建二进制堆只需要O(N)时间.
因此,将每个元素插入到数组(或支持随机访问迭代器的其他容器)中然后在数组上调用make_heap()比在插入时维护堆结构更有意义.