在现代硬件上，最小-最大堆优于二进制堆

堆是一种数据结构，我一直在使用，而其他人不知何故很少使用。(我曾经有一位同事告诉我，他知道有些代码是我的，因为它使用了堆)最近我编写的代码确实可以从使用堆中获益(就像大多数代码一样)，但是我需要能够从两端弹出项。因此，我阅读了有关双端优先级队列以及如何实现它们的内容。这些都很少见，但最常见的实现是“间隔堆”，它可以快速解释，具有干净的代码，并且只比二进制堆稍微慢一点。但是还有一种叫做“最小-最大堆”的替代方法，它没有很漂亮的代码，但是它的依赖链更短，这在现代硬件上很重要。因此，它最终通常比二进制堆更快，即使它允许您从两端弹出。这意味着可能再也没有理由使用二进制堆了。

在我们进入细节之前，先快速刷新一下堆数据结构。它们通常用于优先级队列，但是当您的对象有顺序并且您一次只关心对象的一个子集时，它们通常更有用。假设您只关心前10个项目：堆允许您以较低的成本跟踪前10个项目，即使集合经常被修改。或者，您可能有一个滚动视图，可以滚动到一个很大的项目列表中：不需要对整个集合进行排序。仅对当前可见的选择进行排序，其余部分保留为两堆，以便在添加新项目或用户向上或向下滚动时以较低的成本更新视图。最后，本文提供了一个有趣的视觉用途，您必须快速从所有项目都在不断变化的集合中提取最小值。堆非常适合这样做，但是当您想要更改项时，需要一些额外的存储空间来查找它们在堆中的位置。

你可以把整个收藏品分类。但是排序的开销很大，如果集合经常更改，则排序后的集合的维护成本也很高。

您可以使用像红黑树或B树之类的树数据结构。如果您需要搜索项，它们是一个很好的选择，但除此之外，它们比堆慢。(因为它们必须对集合进行排序才能构建树)。

堆的特别之处在于它的空间开销为零。从字面上看，你只需储存物品。要将集合转换为堆，只需更改项的存储顺序。只要项的父项大于或等于其子项，您就拥有一个堆。索引i的父项位于索引(i-1)/2。索引i的两个子项位于(2*i)+1和(2*i)+2。

要将项添加到堆中，可以将其添加到末尾，然后检查它是否大于其父项。如果是，则插入操作违反了堆属性(父项必须大于或等于其子项)，您必须在父项链上交换该项，直到一切正常为止。

要从堆中删除一个项目，您可以将其与最后一个项目交换，然后从后面弹出。现在，您将交换的项放在了错误的位置，因此您必须向上或向下滴入它，直到堆属性再次有效。(意思是，如果它大于新的父项，则将其交换，如果子项大于新项，则将其与较大的子项交换)。

最大的项目总是在索引0处，删除该项目比删除随机项目要便宜一些，因为您不必检查是否存在涓滴现象。

您还可以通过更改所有比较的顺序来构造最小堆。在这种情况下，最小的项将在索引0处。

这些算法都非常简单，如果您只实现了一次，则始终可以通过记住只需维护堆属性(父级大于或等于其子级)来重新派生它们。

高速缓存问题：这可能是简单的高速缓存未命中，也可能是不同的线程争夺高速缓存线。这是一大类性能问题。

Amdahl定律：您的代码中任何不并行运行的部分都倾向于主宰您的运行时。无论是在使用多线程时的大规模情况下，还是在相关性链破坏指令级并行性时的微观级情况下，这一点都是正确的。

分支预测错误：这比以前的问题要小得多，因为分支预测器非常棒，但是当它真的击中您时，它可能真的会伤害到您。

显然还有更多种类的性能问题，比如做太多的工作或使用错误的算法，但这些都是与硬件相关的最大问题，会对您造成伤害。

堆非常适合于第1类：因为您的空间开销为零，并且因为堆通常只是存储在平面数组中，所以您几乎没有高速缓存问题。当推送一大堆项目时，您将重复访问相同的缓存线，因此即使在大型堆上也会看到良好的性能。但是弹出是不可预测的，可能会在大堆上跳过内存，这可能会导致缓存未命中。但是堆仍然会比其他方法做得更好。

堆对于类别3也很好：同样，推送也很容易：(这将是一个主题)如果您将堆用于优先级队列，通常您将在后面推送，在前面弹出，因此可以正确地预测推送的所有比较结果为false。但是，即使您没有将堆用于优先级队列，并且如果您正在推送完全不可预测的项目，分支预测器也可以做得很好：第一次比较有50/50的机会，因为这取决于您是在上半部分还是下半部分。但下一次预测的准确率为75%，因为如果你在前25%的项目中，你只有两次涓涓细流，如果你在前12.5%的项目中，你只有三次涓滴上升。所以分支预测器只有在那之后才会变得更好。但弹出又变得更难了：你必须找到你的孩子中较大的一个，这将是完全不可预测的：左边的孩子和右边的孩子升迁的可能性相等。但是，您可以通过计算子索引为(2*i)+1+(Child 1<；Child 2)来使其无分支，这样会更快。

堆有问题的地方属于类别2：几乎每条指令都依赖于前一条指令。在堆推送和弹出中，CPU可以执行非常少的指令级并行。在这里，推送再一次稍微容易一些，因为您甚至在知道比较结果之前就可以计算下一个索引，但是弹出则比较困难：您需要知道左或右的子项是否更大才能知道下一个索引，并且您需要知道下一个索引才能开始下一个比较。任何事情都不可能同时发生。

因此，虽然堆通常非常快，但我们现在确实看到了堆的性能仍然可以改进的地方：我们需要对这些依赖链做些什么。但首先，我需要介绍实现双端优先级队列的典型方法：

堆有一个主题，即向堆中添加一些内容很容易，但将数据传回更难。推到后面很便宜，从上面弹出来更贵。插入随机物品很容易，删除随机物品要么需要线性搜索，要么需要额外的簿记才能知道物品在哪里。(有了额外的簿记功能，堆的内存开销不再为零，但仍然非常快)。

所以双端堆的日子不好过：它们想让更昂贵的操作POP变得更强大。不仅从堆中弹出顶部，而且从堆中弹出底部的项也应该很便宜。

维基百科关于这一主题的文章解释了如何使用“间隔堆”来实现这一点，“间隔堆”是一种非常优雅的数据结构：所有偶数索引的项形成一个最小堆，所有奇数索引的项形成一个最大堆。因此，您可以使用普通的堆操作，只是您必须强制执行一个额外的属性：min-heap中的项必须小于或等于max-heap中的匹配项。如果强制执行，则它们定义包含这两个项的所有后代的间隔。(这就是这个名字的由来)它真的很优雅，因为我们有一个比堆更强大的数据结构，但是我们仍然没有空间开销：我们只是对相同的项有不同的排列。它的执行完全符合您的预期：相当快，但比二进制堆稍慢，因为您必须执行正常的堆操作，并与另一个堆中的匹配项进行比较。下面是一个图表，其中我推送了N个项目，然后将时间除以N，得出平均推送时间：

所以间隔堆并不慢，但比二进制堆慢。如果您想知道为什么第一个图形变平，而第二个图形随着容器变大而不断增加：这两个操作的最坏情况下的性能都是O(Logn)，所以您会认为它们会随着容器的大小而增长(请注意X轴上的对数刻度)，但我在这里插入的是随机项，在插入排序项时，您只会遇到推送的最坏情况。当插入随机项时，您有50%的机会往上滴一次，25%的机会往上滴两次，12.5%的机会往上滴三次，等等。这意味着即使堆变大了，做更多工作的机会也会下降。所以曲线图变平了。

但我们来这里不是为了间歇堆。这只是每个人都在使用的数据结构。关于我一直承诺的最小-最大堆，这是怎么回事？

最小-最大堆的概念与间隔堆类似。只是最小-最大堆在每一层上都是交替的。第一、第三、第五等层是最小层，第二、第四、第六等层是最大层。最小层中的项目比它们的所有后代都小。最大层中的项目比它们的所有后代都大。以下是维基百科的一张图片：

这样看起来，不清楚间隔堆有什么好处。如果你看那篇维基百科文章中的伪代码，你会看到类似于“m：=i的最小的子孙的索引”。意思是取索引i，检查最多6个子代，看看哪一个是最小的，然后把它的索引赋给变量m，难怪没人用这个。

但是，由于我已经向您提供了堆在哪里变慢的信息，所以我想让您注意一件事：我们在这里经常可以跳过级别。如果我想要找到上图中根的最小后代8，我可以跳过下一级，只查看8的孙子。这意味着我只需要比较31、10、11和16。还记得依赖链是堆的性能问题吗？我们仍然有同样的问题，但现在链条只有一半长，因为我们只需要看一半的层。当然，我们每层都要做更多的工作，但无论如何我们都没有充分利用CPU的指令级并行性。

在包含N个项的二进制堆上，您最终得到了层，并且必须进行最多的比较。在间隔堆中，您在内部使用两个堆，因此每个堆最终都有层。因此，它只移除一层，以换取每层做更多的工作。在最小-最大堆中，我们可以跳过每隔一层，因此我们只需进行比较。这是一个很大的区别。例如，。这意味着如果这是唯一计算的数字，那么大小为1,000,000的最小-最大堆将与大小为1,000的二进制堆一样快。实际上，好处并不是很大，因为我们必须为最小-最大堆做更多的工作。现在是推送物品的时候了：

因此，在这两种情况下，最小-最大堆都比二进制堆稍微快一些。但请记住，我们在这里不是在比较两个等价的数据结构。最小-最大堆的弹出窗口上有两行：一行用于弹出最小项，另一行用于弹出最大项。因为最小-最大堆严格地比二进制堆更强大。所以它有更多的功能和更快的速度。你多久会遇到这样的事情？

(哦，是的，我还应该为间隔堆画两条线，一条线用于弹出min，另一条线用于弹出max，但是我想把重点放在min-max堆上)。

需要指出的一个细节是，弹出最大值比弹出最小值稍微快一些。至少对图表的某些部分是这样。我认为原因是Popping Max不得不关注较少的层。这很令人惊讶，因为我最初的预期正好相反：POPPING MAX最初需要做更多的工作，因为MAX项目有两个候选项目，但如果您将最初的比较设置为无分支，这最终会变得很便宜，所以少使用一个层的成本节约更有好处。

还有最后一个操作，make_heap()。这是一个O(N)循环，可以快速将任何集合转换为堆。它比反复调用push_heap()快得多。下面是最小-最大堆如何执行此操作：

在这里，最小-最大堆的速度与二进制堆几乎相同，主要是因为二进制堆已经非常快了。(如果您认为与您的体验相比，该二进制堆看起来非常快，那么您刚刚发现我在这里没有使用STL堆。Libstdc++有一个非常慢的make_heap实现，所以为了进行公平的比较，我不得不编写自己更快的make_heap。下面我将解释)早期y轴会跳来跳去，但这不是测量噪音：我选择了一个有点奇怪的y轴：调用make_heap的时间除以堆中的项目数。这使得它更容易与上面的PUSH_HEAP图进行比较，但是它会导致初始的跳变，因为最初的性能特征变化很大：在上面的Make_Heap图中，6个项目的时间为18纳秒，7个项目的时间为20纳秒，8个项目的时间为27纳秒。所以时间增加了，但是我显示的是平均数，第七件商品在这一点上比平均数便宜，所以平均数下降了。然后第八件商品更贵，因为它开始了一个新的层。

最小-最大堆是在1986年发明的，那么为什么没有人使用它呢？答案有点难找，因为没有人使用，导致文献匮乏。Google也很难搜索到最小-最大堆，因为Google只想向您展示有关普通二进制最大堆或普通二进制最小堆的文章。有人用C++实现了一个最小-最大堆，然后说在他实现之后，他发现一篇文章说间隔堆更快，所以他有点放弃了。我想他一定指的是Skov&；Olsen在2001年发表的论文“三个不同优先级Deques的比较分析”，这篇论文看起来很棒(甚至包括源代码)，但是它发现最小-最大堆非常慢。他们的问题是，在可能的情况下，他们不会跳过层的把戏。但是，当一篇明显看起来质量很高的论文(我不是在开玩笑，实际上我认为它是一篇非常高质量的论文)告诉你它很慢时，你会相信它。我很幸运，除了维基百科的文章之外，我没有看到任何东西，而且我一直在考虑如何进一步提高堆的速度。因此，让我们讨论一下如何高效地实现最小-最大堆：

当你推一个东西的时候，你首先要检查你是在最小层还是在最大层。如果堆(包括新项)的长度为1，则位于最小层上。如果堆的长度是2或3，那么您就在最大层上。如果堆的长度是4、5、6或7，那么您就在最小层上，等等。检查这一点的最便宜的方法是使用最高有效位的位置。(至少我找不到更便宜的方法)意思是使用“位扫描反转”指令，然后检查最高有效位是否在偶数或奇数位置。看起来C++20最终添加了一种使用std：：countl_Zero访问该指令的方法。不过我没有C++20，所以我不得不用老的平台特有的方法：微软提供_BitScanReverse64(Size)，但在Linux上你必须这样做(63-__builtin_clzl(Size))。这样做的好处是我验证了我的代码实际上只是调用了“bsr”，其中标准C++版本有一个可能强制它执行分支的接口。(不过这一点不确定，所以如果您能够使用C++20，那么只需检查程序集是否有额外的分支)。

在推送中你要做的下一件事是检查你是否在错误的层中：如果新项目在最小层中，但它比最大层中的父项大，那么你必须交换这两个。(或者反过来，如果新项目从最大层开始)，那么在那之后，你可以通过与你的祖父母进行比较来正常地涓涓细流，总是跳过其间的层。我的实现在这里。我在实现中使用了“goto”，因为我找不到一种方法来组织初始切换，而不必进行额外的比较。我相信有一种方法可以做到这一点，但这看起来并没有那么糟糕，因为这只是最初的切换。

和往常一样，流行音乐变得更难了。弹出最小项的开始与在二进制堆上弹出相同。要弹出最大项，我们需要找到前三个项中最大的一个。如果堆的长度为1，我们将立即完成，因为唯一的项是最大的项。如果堆的长度为2，我们也会立即完成，因为第一个项目在最小层中，所以最大的项目已经在数组的末尾。否则，最大项的索引为1+(heap[1]<；heap[2])。这意味着我们将比较结果转换为整数并将其加到1，以便这里没有分支。在我们找到最大的项之后，我们将其与数组的末尾互换，然后将过去位于末尾但现在位于错误位置的项向下滴入。

向下滴水时，我们希望尽可能跳过层层。幸运的是，除了最后一层之外，所有层都有可能做到这一点。当我们到达一个层，其中要么没有两个子代，要么没有四个孙子代，这意味着我们已经到达迭代的末尾。因此，对迭代结束的检查可以与允许我们跳过层的检查相同。这就给我们留下了两种情况需要处理：一种是常见的情况，当我们有四个孙子孙女，可以跳过一层；另一种情况是，我们可以有任意数量的子孙。

在一般情况下，我们必须找到四个孙子孙女中最小的一个。(在弹出最大项时，只需将我所有句子中的逻辑从“最小”改为“最大”即可。没有其他区别)四个孙子在数组中总是紧挨着彼此，所以这应该很快。要找到N个项目中最小的一个，需要(N-1)个比较，但重要的是我们如何进行比较。如果我们按顺序比较它们(就像std：：min_element那样)，那么我们就有一个从每次比较到下一次比较的依赖链，CPU一次只能做一个。我们可以像这样绘制依赖链：

如果我们将a与b进行比较，将c与d进行比较，然后将BOT的结果进行比较

进行比较的第二种方式还有另一个好处。因为四个孙子孙女都是紧挨着的，所以前两次比较可能是无分支的。第一个是(i+(heap[i+1]<；heap[i]))，第二个是(i+2+(heap[i+3]<；heap[i+2]))。这意味着我们再次将比较结果转换为整数。

然后我的编译器甚至决定将最终的比较转换为有条件的移动，所以整个过程是无分支的。我认为这个分支完全不可预测，所以在这里使用cmov是个好主意。不幸的是，我认为没有办法强制编译器这样做，所以我很幸运。(一)。

.