具有相同元素的最大和最小堆

Question

考虑以下示例。我将随机数添加到最小堆中，同时我将相同数字以相同顺序添加到最大堆中。所以最后这两堆将有相同的数字，其中一个是最小堆，另一个是最大堆。

现在，这里的问题：

如果我决定从最大堆取出的最大元素，将从最大堆总是在最小堆的底部是最大的元素？如果不是，那么另一个问题是，如果我想从最小堆中删除最大元素并将其与最小堆的最后一个元素进行交换，删除最后一个元素，我是否需要运行必须比较该开关元素的操作与他的孩子，以修复分堆？或者将它总是与父母进行比较以修复最小堆？

Answer 1

根据定义的最大堆，根总是大于它的孩子。然而，在儿童中没有特定的顺序，所以左侧的孩子并不总是大于右侧，反之亦然。 max heap的最大元素，即根，必须位于最小堆中的叶子上。我们不知道哪一片叶子，这取决于元素的配置。 （即插入这些元素的顺序，因为通常插入的元素是从树的最左侧到最右侧填充的）