标签: binary-heap

作为Haskell的一个练习,我正在尝试实现heapsort.堆通常在命令式语言中实现为数组,但在纯函数式语言中这将是非常低效的.所以我看了二进制堆,但到目前为止我发现的所有内容都是从命令性的角度描述的,所提出的算法很难转化为功能设置.如何在Haskell等纯函数式语言中有效地实现堆？

编辑:通过有效我的意思是它应该仍然在O(n*log n),但它不必击败C程序.另外,我想使用纯函数式编程.在Haskell中做这件事还有什么意义呢？

Fibonacci堆和二进制堆的真实世界应用是什么？如果你可以在用它来解决问题时分享一些实例,那就太棒了.

编辑:还添加了二进制堆.很想知道.

在我的程序中,我需要从不在顶部的优先级队列中删除一个元素.可以这样做吗？如果没有,请建议一种方法,除了创建自己的堆.

我查看了C++ 0x标准,发现要求make_heap不应超过3*N比较.

即堆积无序集合可以在O(N)中完成

   /*  @brief  Construct a heap over a range using comparison functor.

为什么是这样？

来源没有给我任何线索(g ++ 4.4.3)

while(true)+ __parent == 0不是线索,而是对O(N)行为的猜测

template<typename _RandomAccessIterator, typename _Compare>
void
make_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
          _Compare __comp)
{

  const _DistanceType __len = __last - __first;
  _DistanceType __parent = (__len - 2) / 2;
  while (true)
    {
      _ValueType __value = _GLIBCXX_MOVE(*(__first + __parent));
      std::__adjust_heap(__first, __parent, __len, _GLIBCXX_MOVE(__value),
                 __comp);
      if (__parent == 0)
        return;
      __parent--;
    }
}

__adjust_heap看起来像一个log N方法:

while ( __secondChild < (__len - 1) …

我需要知道二进制和二进制堆之间的主要区别,不管它们的结构差异,二元堆只能有两个子(树表示),二项堆可以有任意数量的子.

我实际上只是想知道组织二项式树结构的特别之处在于第一个孩子在一个节点上有第二个有两个第三个有四个等等吗？

如果我们使用一些普通的树而没有两个孩子的限制然后应用联合过程而只是让一个堆成为其他堆的左子？

我创建了一个二进制堆,它代表一个优先级队列.它只是经典的众所周知的算法.此堆计划不同事件的时间顺序(排序键是时间).

它支持2种操作:插入和删除.堆的每个节点的密钥大于或等于其每个子节点.但是,使用相同的键添加事件不会保留它们的添加顺序,因为每次调用Remove或Insert后,堆启动和堆降过程都会破坏顺序.

我的问题是:在经典算法中应该改变什么以保持具有相同优先级的节点的顺序？

引用维基百科:

使用传统的二叉树数据结构来实现二进制堆是完全可以接受的.在添加可以通过算法解析 的元素时,在二进制堆的最后一级找到相邻元素存在问题 ...

关于这种算法如何工作的任何想法？

我无法找到有关此问题的任何信息,因为大多数二进制堆都是使用数组实现的.

任何帮助赞赏.

最近,我注册了一个OpenID帐户,无法编辑我的初始帖子或评论答案.这就是我通过这个答案回应的原因.非常遗憾.

引用米奇小麦:

@Yse:你的问题是"如何找到二进制堆的最后一个元素"？

是的.或者更确切地说,我的问题是:"我如何找到非基于数组的二进制堆的最后一个元素？".

引用Suppressingfire:

你有没有提出这个问题的背景？(也就是说,你试图解决一些具体问题吗？)

如上所述,我想知道"找到非基于数组的二进制堆的最后一个元素"的好方法,这是插入和删除节点所必需的.

引用罗伊:

对我来说,使用普通的二叉树结构(使用定义为[data,pLeftChild,pRightChild]的pRoot和Node)并添加两个额外的指针(pInsertionNode和pLastNode)似乎是最容易理解的.pInsertionNode和pLastNode都将在插入和删除子例程期间更新,以便在结构中的数据发生更改时保持当前状态.这使O(1)访问结构的插入点和最后一个节点.

是的,这应该有效.如果我没有弄错,找到插入节点和最后一个节点,当它们的位置由于删除/插入而变为另一个子树时,可能会有点棘手.但我会试一试.

引用Zach Scrivena:

如何进行深度优先搜索......

是的,这将是一个很好的方法.我也会尝试一下.

我还在想,如果有办法"计算"最后一个节点和插入点的位置.具有N个节点的二进制堆的高度可以通过获取大于N的最小二次幂的log(基数2)来计算.也许可以计算最深级别上的节点数.然后可能确定如何遍历堆以到达插入点或节点以进行删除.

考虑一个包含n个数字的二进制堆(根存储最大数量).给出正整数k <n和数字x.您必须确定堆的第k个最大元素是否大于x.您的算法必须花费O(k)时间.您可以使用O(k)额外存储空间

有人可以解释一下我应该如何决定是否使用一个或另一个堆实现,在标题中提到的那些？

根据问题,我想要一个答案来指导我选择有关结构性能的实施方案.现在,我正在做一个优先级队列,但我想知道这个案例最合适的实现,但是基本允许我在任何其他情况下选择一个实现...

另外需要考虑的是我这次使用的是haskell,所以,如果你知道任何可以改善这种语言实现的技巧或其他东西,请告诉我!但和以前一样,欢迎使用其他语言的评论!

谢谢!对不起,如果问题太基础,但我根本不熟悉.这是我第一次面临实施一项任务的任务......

再次感谢!

这是我最近遇到的面试问题之一.

给定完整或几乎完整的二叉树的根地址,我们必须编写一个函数将树转换为最大堆.

这里没有涉及数组.树已经建成了.

例如,

              1   
         /         \
        2           5
      /   \       /   \ 
     3      4    6     7

可以有任何可能的最大堆作为输出 -

              7   
         /         \
        3           6
      /   \       /   \ 
     2     1     4     5

要么

              7   
         /         \
        4           6
      /   \       /   \ 
     2     3     1     5

等等...

我写了一个解决方案,但使用了前后顺序遍历的组合,但我想在O(n ^ 2)中运行.我的代码提供了以下输出.

              7   
         /         \
        3           6
      /   \       /   \ 
     1     2     4     5

我一直在寻找更好的解决方案.有人可以帮忙吗？

编辑:

我的守则

void preorder(struct node* root)
{    
    if(root==NULL)return;
    max_heapify(root,NULL);
    preorder(root->left); 
    preorder(root->right);
}
void max_heapify(struct node* root,struct …