java - 如何区分属于最大堆的元素和属于最小堆的元素？

Question

这段摘录自 Cracking the Coding Interview 第 5 版

Numbers are randomly generated and stored in an (expanding) array. How would you keep track of the median

作者向我们展示了一个基于堆的解决方案:

A heap is really good at basic ordering and keeping track of max and mins. This is actually interesting - if you could keep track of the bigger half and the smaller half of the elements. The bigger half is kept in a min heap, such that the smallest element in the bigger half is at the root. The smaller half is kept in a max heap such that the biggest element of the smallest half is at the root. Now with these data structures, you have the potential median elements at the root." If the heaps are no longer the same size, you can quickly "rebalance" the the heaps by popping an element off the heap and pushing it to the onto the other

我有几个关于这种方法的问题，我一次问一个问题，以使其井井有条。首先，使用这种方法，如果您遍历数组中的元素，您如何知道特定元素属于算法描述的最小堆或最大堆？假设我们的数据元素是 [20, 39, 14, 7, 86, 90]。当你迭代数组时，你会放什么堆，比如说 20？

Answer 1

每次插入元素时，检查最小堆的最小值和最大堆的最大值，以查看每个元素属于哪个堆。

当您看到 20 时，两个堆都是空的，所以这无关紧要 - 假设出现平局，我们会将元素放入较小元素的最大堆中。

[20][]

当你看到 39 时，它比 20 大，所以它在上层堆中

[20] [39]

14 小于 20，所以它在较低的堆中

[14, 20] [39]

7小于20，所以进入下堆，但是现在下堆太大了，所以20从下堆出来，进入上堆。

[7, 14] [20, 39]

86 > 20，所以进入上层堆

[7, 14] [20, 39, 86]

90 > 20，所以进入上堆，但是现在上堆太大了，所以20从上堆出来，又回到下堆

[7, 14, 20] [39, 86, 90]

以何种方式获得平衡并不重要——也许你应该坚持下层堆的大小 <= 上层堆的大小，反之亦然——但你需要保持平衡。