此摘录自《破解编码访谈》第五版
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？
最佳答案
每次插入元素时，请检查最小堆的最小值和最大堆的最大值，以了解每个元素属于哪个堆。
当您看到 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]
哪种方式实现平衡并不重要——也许你应该坚持下堆的大小 <= 上堆的大小，反之亦然——但你需要保持平衡。
关于java - 如何识别属于最大堆的元素和属于最小堆的元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27679573/