批量加载最小-最大堆
最小-最大堆是一种堆，它可以在O(1)中找到最小和最大元素，并在O(log n)中删除它。它与经典堆密切相关，但它实际上交错了三个堆:一个最小堆和两个最大堆，其中偶数级别是最低级别，奇数级别是最大级别(因此有两个根)。经典的堆属性适用于孙子类而不是子类。min- max -heap的叶子级别本质上是在min和max堆之间共享的，此处插入的新元素可以移动到树的偶数或奇数级别。
虽然向上筛选和向下筛选是简单的修改，但当元素需要从堆的最小排序部分移动到最大排序部分时，就会出现棘手的部分。
对于典型的堆，我可以通过执行自下而上的堆修复来在O(n)中批量加载树，而显而易见的逐个插入需要O(n log n)时间。对于批量插入，我也可以这样做，而不是逐个插入它们，我可以将它们全部追加并批量修复堆。
对于最小-最大堆，我当然可以在O(n log n)中线性加载它，但我想知道是否也有一种方法可以在O(n)中批量加载它，或者自下而上地批量修复堆？
回答 2
Stack Overflow用户
发布于 2012-07-30 00:44:16
我将用我到目前为止的发现来回答我自己，对于其他可能有同样问题的人来说：
最小-最大堆本质上是三合一的堆，具有共享的叶级别。
min1 <--- one min heap, first level
/ \
mi2 mi3 <--- third level
/ \ / \
m5 m6 m7 m8 <--- fifth level
/\ /\ /\ /\
a b c d e f g h <--- leaf level (here: sixth level)
\/ \/ \/ \/
x1 x2 x3 x4 <--- fourth level
\ / \ /
max1 max2 <--- two max heaps, second level(重要说明:这并不准确，因为堆的扇出值是4！此外，这是逻辑顺序，而不是内存布局，它在级别上交错堆)叶级别的对象属于所有三个堆，这是元素从堆的最小部分转换到最大部分的地方。
现在可以计算最小堆和最大堆的大小，使用quickselect等部分排序对数据进行分区，并分别批量加载这三个部分。然而，quickselect已经和你想要的整个批量加载一样昂贵了(部分排序数据集)！另一种明显的批量装载和批量修复方法(!)堆将查看较小的子堆。在常规的最小堆中，您将查看由三个元素a、b、c组成的原子堆，并确保a是最小的。在这里，我们可以查看高度为4的堆，即15个元素：
min1
/ \
max1 max2
/ \ / \
m1 m2 m3 m4
/\ /\ /\ /\
a b c d e f g h并确保min1是最小的，max1和max2是两个最大的，m1-m4是下一个4个最大的，并以两个级别的步骤向上爬树(即仅限最小级别)
或者，我们可以查看大小为7 (3个级别)的堆，并区分min和max类型
min1 max1
/ \ / \
max1 max2 min1 min2
/\ /\ /\ /\
a b c d a b c d确保对于最小级别我们有第一种类型，对于最高级别我们有第二种类型。然后我们需要通过所有级别。
但也许更好的解决方案是使用interval heaps。这本质上也是一个交错的最小和最大堆。但是，它们是对称交错的，并且具有相同的大小。它们看起来更容易实现，并且可以解释为如下所示的堆：
min1,max1
/ \
min2,max2 min3,max3有关大容量加载的详细信息，请参阅原始的间隔堆发布。
所以，如果你对可批量加载的最小-最大堆感兴趣，可以考虑考虑使用间隔堆！有些人说他们的性能要优于最小-最大-堆；它们是密切相关的，应该更容易实现。特别是，没有明显的理由说明为什么min-max-heap应该表现得更好，如果详细的复杂性分析表明，在所需的比较和交换中，它们的性能更差，我也不会感到惊讶(因为据我所知，min-max-heap需要更多的比较来验证堆的正确性)。
Stack Overflow用户
发布于 2012-07-25 18:37:31
我相信自下而上的树修复应该是可行的：
def heapify(N)
if (N is a min-node)
if(*N > *left_child(N))
swap(*N, *left_child(N))
if(*N > right_child(N))
swap(*N, *right_child(N))
find the smallest X among N, grand-children(N)
else
if(*N < left_child(N))
swap(*N, *left_child(N))
if(*N < right_child(N))
swap(*N, *right_child(N))
find the largest X among N, grand-children(N)
if(X != N)
swap(*X, *N)
heapify(X)
load heap in arbitrary order
for each N in bottom-up order of heap
heapify(N)https://stackoverflow.com/questions/11646126
复制相似问题
腾讯云开发者
