我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合公式 > 仿函数 >

java stl priorityq 是通过heap实现的吗

归档日期:06-16       文本归类:仿函数      文章编辑:爱尚语录

  下面的_First与_Last为可以随机访问的迭代器(指针),_Comp为比较函数(仿函数),其规则——如果函数的第一个参数小于第二个参数应返回true,否则返回false。

  默认是建立最大堆的。对int类型,可以在第三个参数传入greaterint()得到最小堆。

  新添加一个元素在末尾,然后重新调整堆序。也就是把元素添加在底层vector的end()处。

  该算法必须是在一个已经满足堆序的条件下,添加元素。该函数接受两个随机迭代器,分别表示first,end,区间范围。

  关键是我们执行一个siftup()函数,上溯函数来重新调整堆序。具体的函数机理很简单,可以参考我的编程珠玑里面堆的实现的文章。

  这个算法跟push_heap类似,参数一样。不同的是我们把堆顶元素取出来,放到了数组或者是vector的末尾,用原来末尾元素去替代,然后end迭代器减1,执行siftdown()下溯函数来重新调整堆序。

  注意算法执行完毕后,最大的元素并没有被取走,而是放于底层容器的末尾。如果要取走,则可以使用底部容器(vector)提供的pop_back()函数。

  既然每次pop_heap可以获得堆中最大的元素,那么我们持续对整个heap做pop_heap操作,每次将操作的范围向前缩减一个元素。当整个程序执行完毕后,我们得到一个非降的序列。注意这个排序执行的前提是,在一个堆上执行。

  优先队列(priority_queue)首先是一个queue,那就是必须在末端推入,必须在顶端取出元素。除此之外别无其他存取元素的途径。 内部元素按优先级高低排序,优先级高的在前。缺省情况下,priority_heap利用一个max-heap完成,后者是一个以vector表现的完全二叉树。 我们说优先队列不是一个STL容器,它以底部容器而实现,修改了接口,形成另一种性质,这样的东西称之为适配器(adapter)。详情参见:

  这时我们可以传入一个比较函数,使用functional.h函数对象作为比较函数。

  2.自定义一个比较“类”,重载括号,operator (),这这种方式可以由less“继承”。

本文链接:http://renfriends.com/fanghanshu/643.html