二进制堆的有效实现

我在寻找如何有效地实现二进制堆的信息 。 我觉得应该有一个好的文章有关实施堆,但我还没有find一个。 事实上我一直没有find任何有关如何将数据堆存储在基础之上的有效实现方面的资源。 我正在寻找制作快速二进制堆的技术,超出了我在下面描述的范围。

我已经写了一个比Microsoft Visual C ++和GCC的std :: priority_queue更快的C ++实现,或者使用std :: make_heap,std :: push_heap和std :: pop_heap。 以下是我在实现中已经涉及到的技术。 我自己只提出了最后两个,但我怀疑这些是新的想法:

(编辑:增加内存优化部分)

  • 从1开始索引
    查看二维堆的维基百科实现注释 。 如果堆的根位于索引0处,则索引n处的父节点,左节点和右节点的公式分别为(n-1)/ 2,2n + 1和2n + 2。 如果使用基于1的数组,那么公式将变得更简单n / 2,2n和2n + 1.因此,在使用基于1的数组时,父项和左项是更高效的。 如果p指向一个基于0的数组,并且q = p-1,那么我们可以像q [1]那样访问p [0],所以在使用基于1的数组时没有开销。
  • 在更换叶子之前,将popup/移除元素移到堆的底部
    在一个堆上popup通常是通过replace最左边的底部叶子的顶部元素,然后将其向下移动直到堆属性被恢复来描述。 这要求每个级别进行2次比较,而且我们可能会在堆栈顶部移动一个叶子,因此可能会走得很远。 所以我们应该期望有less于2个log n的比较。
  • 相反,我们可以在堆顶部留下一个洞。 然后,我们通过迭代地将更大的孩子向上移动,将这个洞向下移动。 这只需要我们通过每个级别1比较。 这样孔就会变成一片叶子。 在这一点上,我们可以将最右边的底部叶子移动到洞的位置,并移动该值直到堆属性恢复。 既然我们移动的价值是一片叶子,我们不期望它移动到树上很远。 所以我们应该期待比log n比较多一点,这比以前更好。

  • 支持replace顶部
    假设你想删除最大的元素,并插入一个新的元素。 然后,您可以执行上述的删除/popup实现,但不是移动最右侧的底部叶,而是使用您希望插入/推送的新值。 (当大多数操作都是这种types的时候,我发现比赛树比堆好,但是堆好一些。)
  • 使sizeof(T)为2的幂
    父母,左孩子和右孩子的公式在索引上工作,不能直接在指针值上工作。 所以我们将要使用索引,这意味着在索引i的数组p中查找值p [i]。 如果p是一个T *,而i是一个整数,那么
  • &(p[i]) == static_cast<char*>(p) + sizeof(T) * i 

    编译器必须执行这个计算才能得到p [i]。 sizeof(T)是一个编译时间常量,如果sizeof(T)是2的幂,乘法可以更有效地完成。 我的实现通过添加8个填充字节来将sizeof(T)从24增加到32来得到更快的速度。降低caching的效率可能意味着这对于足够大的数据集来说不是赢。

  • 预乘法索引
    我的数据集增长了23%。 除了寻找父母,左孩子和右孩子之外,我们唯一的一个索引是用数组来查看索引。 所以,如果我们跟踪j = sizeof(T)* i而不是索引i,那么我们可以做一个查找p [i],而不需要在计算p [i]时隐含的乘法,因为
  •  &(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j 

    然后,j值的左孩子和右孩子公式分别变为2 * j和2 * j + sizeof(T)。 父母的公式有点棘手,我还没有find一种方法来做到这一点,除了将j值转换为i值,并返回像这样:

     parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T) 

    如果sizeof(T)是2的幂,那么这将编译成2个class次。 这比使用索引i的常用父项多1项操作。 但是,我们然后保存1查找操作。 所以最终的效果是,find父母的时间相同,而左右儿童的查找速度更快。

  • 内存优化
  • TokenMacGuy和templatetypedef的答案指出了基于内存的优化,减less了caching未命中。 对于非常大的数据集或不经常使用的优先级队列,队列的一部分可以由操作系统换出到磁盘。 在这种情况下,为了更好地使用caching,需要增加大量开销,因为从磁盘交换非常缓慢。 我的数据很容易适应内存,并且可以连续使用,所以队列中的任何部分都不会被交换到磁盘。 我怀疑大多数优先队列的使用是这种情况。

    还有其他优先级队列可以更好地利用CPUcaching。 例如,一个4堆应该有更less的caching未命中和额外的开销额是没有那么多。 LaMarca和Ladner在1996年报告说,他们得到75%的performance改善,从而达到一致的4堆。 但是, Hendriks在2010年报告说:

    对LaMarca和Ladner [17]提出的改进数据局部性和减lesscaching未命中的隐含堆的改进也进行了testing。 我们实现了一个四路堆,对于非常偏斜的input数据,其确实显示出比双向堆略好的一致性,但只适用于非常大的队列大小。 非常大的队列大小最好由分层堆处理。


  • 有比这更多的技术吗?
  • 4 Solutions collect form web for “二进制堆的有效实现”

    关于这个主题的一篇有趣的论文/文章考虑了堆的整体布局上的caching/分页的行为; 这个想法是,比起数据结构实现的任何其他部分来说,支付caching缺失或者页面成本要高得多。 本文讨论了解决这个问题的堆布局。

    你正在做错Poul-Henning Kamp

    作为@ TokenMacGuy的文章的阐述,你可能想看看caching遗忘的数据结构 。 这个想法是构build数据结构,对于任意的caching系统,最小化caching未命中的数量。 它们很棘手,但是从你的angular度来看它们可能是有用的,因为即使在处理多层caching系统(例如,寄存器/ L1 / L2 / VM)时它们也performance良好。

    实际上有一篇文章详细介绍了一个最佳caching优先级队列 ,可能会引起人们的兴趣。 这个数据结构在速度方面会有各种各样的优点,因为它会尽量减less每个级别的caching未命中数量。

    我不知道你是否错过了二进制堆的wiki页面上的这个链接,或者你认为它不值得,但是无论如何: http : //en.wikipedia.org/wiki/B-heap

    第一点:即使有一个“备用点”为您的基于arrays的实施是不是浪费。 无论如何,许多操作都需要临时元素。 每次在索引[0]处使用一个专用的元素,而不是每次都初始化一个新的元素。

  • 如何从增强现实开始?
  • “closures”和“块”之间究竟有什么区别?
  • math计算机科学
  • 理解neural network反向传播
  • 什么是y-组合器?
  • 什么是recursion,什么时候应该使用它?
  • 检测树结构之间的差异
  • 什么是较less的已知但有用的数据结构?
  • 图灵机vs冯·诺依曼机器
  • 哈希代码和校验和 - 有什么区别?
  • 什么时候使用Preorder,Postorder和Inorder二叉search树遍历策略