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

Question

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

现在问题来了：

如果我决定从最大堆中删除最大元素，那么最大堆中的最大元素是否总是在最小堆的底部？如果不是，那么另一个问题是，如果我想从最小堆中删除该最大元素，并将他与最小堆的最后一个元素交换，删除最后一个元素，我是否需要运行必须比较该切换元素的操作带着他的孩子为了修闵堆？还是总是将其与父级进行比较以修复最小堆？

Answer 1

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