Get best of the week

弱堆排序


在整个动物园堆中，这种结构也许是最不寻常的。同时，该算法的优雅简洁性与其惊人的偏心率非常匹配。

使用弱堆进行排序时，总是比使用常规堆进行的比较和交换少。因此，是的，弱桩比普通桩要坚固。
EDISON软件-网络开发
本文是在EDISON的支持下编写的。

我们从事嵌入式软件的开发以及Web应用程序和站点的开发。

我们喜欢算法理论！;-)

弱桩


常规堆是一个排序树，其中任何父项大于（或等于）其任何后代。在弱堆中，此要求被削弱了-仅从其右子树开始，任何父项都大于（或等于）任何后代。在左侧的子树中，后代可以比父代小一些，也可以更大一些，那真是太幸运了。


这种方法可以显着降低将数据集保持在堆状态的成本。毕竟，有必要确保“后代只不过是父母”这一原则不适用于整个结构，而只适用于其一半。同时，不是100％排序树的弱堆排序不会比普通堆差，并且在某些方面甚至更好。完成了一半的比赛-大胆行走！

由于堆的根，即使是弱堆，也恰好需要最大的元素，因此左子树的根不需要。

尽量减少比较次数



算法和图论专家Ronald D.Dutton在1993年向我们展示了一个薄弱环节。概念上较弱的堆比普通堆更难理解（但这种困难很可能不是复杂的，而是奢侈的，您必须通过膝盖来破坏意识模式），因此它没有得到太多实际的分配。但是，当达顿（Dutton）发明这种结构时，他不仅想练习抽象，而且还追求一个完全务实的目标。

有一个理论上的下限来估计比较的最小数量（在这些比较被广泛使用的排序中）：

log n！= n log n - n / ln 2 + O（log n），其中1 / ln 2 = 1.4426

在按弱堆进行排序时，比较次数被最小化并且足够接近下限。

如果您需要安排比较成本很高的对象（例如，涉及对长字符串进行排序），那么这可能具有实际意义。

杂耍后裔


弱堆中的“左”和“右”是一种情况现象。子树可以是其父节点的左后代或右后代-而且，子树的这种“左/右”关系，并且在此过程中父级可以反复从一个值切换为相反的值。

要为有他的右儿子和他的左女儿的父母做指示并不简单，但是非常简单。为此，对于具有后代的那些节点，您需要一个附加的位图（仅包含0/1值）。

回想一下第i个父元素的索引，我们定义了它在常规堆中的左后代和右后代的索引（数组的索引从零开始测量）：

左后代2× i + 1
右后代2× i + 2

在弱堆中，我们在蛋糕上有一个樱桃-根只有右子树，因此我们将反向移位添加到1位置，以调整后代索引的这些公式：

左后代：2× i
右后代：2× i + 1

最后需要额外的位图（称为bIT），其中第i个元素是在其左子树和右子树之间是否进行交换。如果元素的值为0，则没有交换。如果值为1，则左，右子级的顺序相反。并且在这种情况下的公式如下：

左后代：2× i + BIT [ i ]
右后代：2× i +1- BIT [ i ]

这是它的外观。其后代位于“反之亦然”的元素以蓝色突出显示。它们在BIT数组中的值为1。


您可以通过在后代公式中从BIT数组中替换父值i和相应的0/1来进行检查- 后代的索引将根据需要显示。 如您所见，对于任何父代来说，在数组本身中交换左右子树，都不需要将元素组移动到任何地方。仅切换BIT数组中父级的0/1值即可。 接下来-一场魔术，其后的曝光。





建立弱桩


左右交换是将数组中的一组数据转换为弱堆的主要工具。

在形成主要的弱堆的过程中，我们需要以相反的顺序（从最后一个开始）对数组的元素进行排序，并为每个元素找到第一个（正确的）父代的分支，对于它来说它将是正确的子树。

如果元素是某人的正确后代，那么您不必走太远。它的直接父项是您需要的：


如果该元素是某人的左后裔，那么您需要先达到多个层次，然后再遇到所需的祖父母，该元素位于右侧的子树中：



然后，您需要比较后代和上方找到的祖先。如果后代大于祖代，则必须执行以下操作：

  1. 如果后代有其后代，则交换其左和右子树（即，此元素在BIT阵列中切换0/1 ）。
  2. 交换后代节点和祖代节点的值。

看一个具体的例子。假设发生了以下情况：


对于数组A [6] = 87 的元素，找到了必要的祖先A [1] = 76。
祖先A [1]小于元素A [6]（76 <87）。
元素A [6]具有左右子树（以绿色阴影标记）。
您需要交换这些子树
（即，对于BIT数组中的元素A [6]，将值从0更改为1）。 也有必要交换元素A [6]和A [1]的值。


完成必要的操作后：


对于元素A [6]，交换了左和右子树
（即，在元素A [6] 的BIT数组中，值从0更改为1）。A [6]和A [1] 之间也进行了价值交换。


如果您从头到尾遍历整个数组，并一路对所有元素执行此过程，那么最终将得到一个弱堆。

为什么这种奇怪的机制起作用，这是本文结尾处的一个解释。

解析弱堆


如果最大元素位于根，则堆就是堆。利用这个事实，所有堆排序都以相同的方式进行。根（最大值所在的位置）与数组未排序部分的最后一个元素交换值-结果是，数组未排序部分减少，数组的排序部分增加。交换之后，该堆不再是堆，因为当前的最大元素不再在其根中。需要恢复堆，也就是说，将生成的树再次变为堆-找到另一个最大元素并将其移到根。

我们知道如何在筛子的帮助下恢复常规的二进制堆。但是如何恢复弱堆呢？为此，请执行以下操作。

从根开始，我们沿左后裔下降（从右至上）。


然后我们将左后代上移，然后将每个左后代与堆根中的一个元素进行比较。并且如果下一个左后代大于根，则我们与上一阶段相同：在左后代我们交换子树（如果他有一个子树）并更改左后代和根的值。

结果，我们将还原弱堆-其余树中的最大元素将在其根处弹出。

再次，我们有这个神秘的轮播，其子树可以互相替换。那么成功的秘诀是什么？为什么在交换带有值的节点时，下层节点的左后代和右后代互换了，我们最终得到一个排序数组吗？尽管答案很简单，但您永远也不会猜到。

弱堆排序::弱堆排序


因此，最终的算法是：

  • I. :
    • I.1. -.
    • I.2. «» .
    • I.3. .
    • I.4. , :
      • I.4.. ( ⇔ ) , .
      • I.4.. «» .
  • II. , :
    • II.1. .
    • II.2. . .
    • II.3. , . :
      • II.3.. .
      • II.3.. , .
      • II.3.. , , :
        • II.3.c.1。我们将子树与子树交换（左⇔右）子树，以替换当前左子孙所在的节点。
        • II.3.c.2。我们使用当前的左子节点更改堆根和节点。
    • II.4。弱堆的根再次是数组其余未排序部分的最大元素。我们回到第II.1段，重复该过程，直到所有元素都被排序为止。


动画（我的动画中的数组索引以1开头）：



C ++代码


在“链接”部分的底部，有兴趣的人可以熟悉C ++中这种排序的实现。在这里，我仅给出说明算法本身的部分。

#define GETFLAG(r, x) ((r[(x) >> 3] >> ((x) & 7)) & 1)
#define TOGGLEFLAG(r, x) (r[(x) >> 3] ^= 1 << ((x) & 7))

void WeakHeap::WeakHeapMerge(unsigned char *r, int i, int j) {
  if (wheap[i] < wheap[j]) {//""  ?
    //  ,   
    //( "",   "")
    TOGGLEFLAG(r, j);
    //  ""  
    swap(wheap[i], wheap[j]);
  }
}

void WeakHeap::WeakHeapSort() {
  int n = Size();
  if(n > 1) {
		
    int i, j, x, y, Gparent;
    int s = (n + 7) / 8;
    unsigned char * r = new unsigned char [s];
		
    //  ,    
    // "",   ""
    for(i = 0; i < n / 8; ++i) r[i] = 0;
		
    //   
    for(i = n - 1; i > 0; --i) {
      j = i;
      //    , 
      //   ""  
      while ((j & 1) == GETFLAG(r, j >> 1)) j >>= 1;
      //       ""  
      Gparent = j >> 1;
      //  ,   
      //   ""
      WeakHeapMerge(r, Gparent, i);
    }
		
    //      -->
    //  -->    
    for(i = n - 1; i >= 2; --i) {
      //      
      //       
      swap(wheap[0], wheap[i]);
      x = 1;
      //    "" 
      while((y = 2 * x + GETFLAG(r, x)) < i) x = y;
      //  ""     
      //        
      while(x > 0) {
        WeakHeapMerge(r, 0, x);
        x >>= 1;
      }
    }
    //  -   
    //    
    swap(wheap[0], wheap[1]);
    delete[] r;
  }
}

我特别喜欢如何使用按位运算轻松自然地遍历二叉树。

额外的内存复杂性


似乎O（n）-需要一个附加数组，其中对于具有后代的节点（该数组中大约有一半的节点），左/右子树的顺序是固定的。

但是，有一种观点认为这里的排序复杂度实际上是O（1）！对于一个元素，我们仅需要一个附加位（零/一）来指示后代的顺序。例如，如果我们对字符串进行排序，那么将这个额外的位附加到元素本身是很可行的。

将O（n）转换为O（1）的另一种方法是将标记存储为整数。数字的二进制扩展-一组零和一个负责数组所有元素的子树的顺序。数组的第i个元素对应于数字的第i个位。

时间复杂度


按时间，O（n log n）与常规堆相同。对行（尤其是长行）进行排序时，弱堆可能比常规堆快。但这是我们对长行进行排序的情况。如果我们对数字进行排序，那么根据传言，普通堆的管理速度更快。

充分筛选


与通常的堆类似，在初始弱堆的形成阶段，相当明显的想法建议将较大的元素提高到尽可能高的水平。也就是说，如果我们交换下层节点及其祖先的值，那么立即对祖先重复步骤是合乎逻辑的-为他找到他最近的右祖先并进行比较（并且如果还需要交换值+交换子树）。并且，如果可能的话，从根本上提出一个大的要素。这是第一阶段的样子（算法第二阶段的操作未更改）：


时间复杂度分数保持不变。

二项式桩


至此，所有的一切都是一种欺骗，一种幻想。当然，我们对那里的二叉树进行正式的操作，用值更改节点，重新排列子树等等。但是，该算法有一个双重底，我们现在将对其进行研究。

要理解这种类型，您需要了解什么是弱堆。

如果我们采用一个数组，其中元素数是2的幂，则弱堆和基于其构造的二项式堆是同构的。


不要看弱堆是二进制，而二项式不是。在弱堆中，左和右子树本质上是不同的。右子树是传统意义上的后代，而左子树则是“兄弟”。虽然没有。左子树甚至不是“兄弟”，而是具有更少节点的“兄弟”的向量。

但是，弱堆和二项式堆虽然是最接近的亲戚，但并非100％相同。如果采用的数组的元素数不等于2 n，则区别是显而易见的。这样的数组的二项式分解将给出几个理想堆的连接列表（每个堆中的节点数是2的一定乘方）：


在这种情况下，弱堆将是一棵不完善的二叉树：



二项式堆和弱堆是双胞胎兄弟。DNA是一样的，尽管从外观上你看不出来。

秘密算法


鉴于弱堆是密码二叉堆，混排子树突然找到了一个简单的解释。


对于较弱的堆，请清除伪二进制金属丝，然后查看二项式堆样式中的节点之间的真实关系。一切都变得清晰起来。

事实上：

  1. 没有“弱点”，它是一种成熟的排序（非二进制）树，其中实现并维护了“任​​何父代大于任何后代”的原则。
  2. 在所有阶段，我们都不将后代与其祖先进行比较，而是与其直系父母进行比较。
  3. 看起来像是后代与祖先之间的价值交换+子代中子树位置的交换-事实是比率本身（后代/父代）的交换。如果父节点的值小于子节点的值，则父节点本身将成为子节点，而子节点将成为父节点。

这是一个诚实的可视化：



在下一个系列中


我想谈的下一堆是我最喜欢的-笛卡尔树。这不仅是一堆，而且是二叉搜索树。但是首先，在下一篇文章中，需要澄清一些有关BST树的有趣信息。直到那时，通过这篇文章，以及关于笛卡尔的话题。

参考文献


弱堆，二项式堆 / 二项式

堆C ++弱堆实现

Ronald D.Dutton： 个人页面，UCF网站配置文件

弱堆和朋友：最新动态

弱堆数据结构：

WEAK-HEAPSORT

自适应性能的变体和应用heapsort：源代码

Sergey Kopeliovich-演讲厅-弱堆（从48:32到1:16:06）

系列文章：




今天的排序是由一小撮人添加到AlgoLab应用程序中的，他们使用它-用宏更新excel文件。

在带有排序名称的单元格注释中，可以指定一些设置。如果将siftup设置为1，则排序将在第一阶段使用完整筛选（默认情况下siftup = 0）。

如果您指定二项式= 1，则树将是“二项式堆”（默认情况下，二项式= 0，即只是一个弱堆）。

More articles:


All Articles