今天在网上刷了一道关于堆的题，感觉有所收获。因为在这里之前，之前从来没有接触过关于堆的题目。
1. 概览
(1).题意
给定一个包含 n 个整数的数组，和一个大小为 k 的滑动窗口,从左到右在数组中
滑动这个窗口，找到数组中每个窗口内的中位数。(如果数组个数是偶数，则在
该窗口排序数字后，返回第 N/2 个数字。)
(2).样例
对于数组 [1,2,7,8,5], 滑动大小 k = 3 的窗口时，返回 [2,7,7]
最初，窗口的数组是这样的：
[ | 1,2,7 | ,8,5] , 返回中位数 2;
接着，窗口继续向前滑动一次。
[1, | 2,7,8 | ,5], 返回中位数 7;
接着，窗口继续向前滑动一次。
[1,2, | 7,8,5 | ], 返回中位数 7;
最初看到这个题，想到的方法是暴力，将给定的窗口里面数字从先到大排序，再去中间那个数就行了。但是，到后面发现超时了。于是乎，在网上搜索了相关解法，网上大多数使用的是用优先队列来操作。基本思路：用两个优先队列来模仿大顶堆和小顶堆（关于大顶堆和小顶堆的含义，这里不再详细的解释），然后操作两个队列里面的数据，选出中位数。
2.解题思路
(1).优先队列
用一个优先队列模仿大顶堆，用来装已经在窗口里面的数字的小的那一半，另一个队列则是小顶堆，装另一半。于是乎，剩下的那一个(没有进入任何一个队列)就是中位数
(2).最初的添加数据
我们假设两个队列在初始化都是空的，同时最初的时候，窗口的里面什么数据都没有，并且将当前的中位数设置为即将进入窗口的那个数。所以我们默认，向窗口加入数据是从第二个开始。
当我们加入一个数据时，判断它与当前的中位数(第一个数据作为中位数)的大小，如果它大于当前的中位数的话，则将它放入小顶堆；反之则放入大顶堆。放入过后(不论是大顶堆还是小顶堆)，判断大顶堆的size与小顶堆的size，如果大顶堆的size大于小顶堆的size，则将当前的中位数放入小顶堆，从大顶堆取出一个数据(poll)作为新的中位数；如果小顶堆的size - 1都大于大顶堆的size，那么将当前的中位数放入大顶堆，从小顶堆中取出一个数据作为新的中位数。如图所示：
问题： 为什么这里大顶堆的size大于小顶堆size就调整，而小顶堆的size - 1大于大顶堆的size才调整呢
我们先来看看题：如果数组个数是偶数，则在该窗口排序数字后，返回第 N/2 个数字。这里说，如数字个数为偶数，则取 N/2。例如：窗口中有3个数字：1 2 3， 那中位数是 2，这个没有争议；但是如果窗口有4个数字：1 2 3 4 ，按照题意，选择 N/2,则是2，也就是说当前大顶堆为：4，而小顶堆：1 2。所以在小顶堆的size - 1大于大顶堆的size才调整，因为如果不调整的话，当前的中位数与当前窗口的数字的中位数不符合，因为窗口在这之前已经加入一个数字。
而加入一个数字，中位数有两种结果：当两个顶堆的size相等或者小顶堆的size - 大顶堆的size = 1时，中位数不变，因为两个顶堆的size平衡(我们可以这样认为，当前窗口中数字小的那一半在窗口的左边，大的那一半放在窗口的右边，而中位数在两个顶堆中间)；当大顶堆的size大于小顶堆的size，表示实际的中位数偏向了大顶堆，所以将当前的中位数放入小顶堆去，从大顶堆中取出最大值作为当前的中位数(大顶堆中的所有数字小于当前的中位数，小顶堆的所有数字大于当前中位数，所以将当前的数字放入大顶堆)。总之一句话，就是加入一个数字后，必须保证当前的中位数就是实际的中位数。如图所示
(3).后续的添加数据
首先我们按照最初的添加数据步骤中得出的中位数，根据前面的规则来添加数据。
当添加一个过后，我们必须在两个顶堆中任意一个移除一个数据，这样才能保证当前窗口显示的数字。我们知道肯定移除当前窗口的第一个，怎么移除呢？首先当前窗口的第一个的值，这个值与当前的中位数来比较，如果大于中位数，则这个值在小顶堆中，从小顶堆移除就是了；如果小于中位数，表示这个值在大顶堆中，从大顶堆中移除；当等于中位数时，则判断当前小顶堆的size与大顶堆的size，如果大于大顶堆，则从小顶堆中取出一个数据作为新的中位数；反之，从大顶堆取出一个数据作为新的中位数
问题：为什么当移除那个值与当前的中位数相等，要这样操作？
首先经过前一次添加数据，大顶堆的size与小顶堆的size要么相等，要么大顶堆的size - 小顶堆的.sze = 1。而这一次添加数据后，要么加入大顶堆，要么加入大顶堆，根据size判断，当大顶堆的size >= 小顶堆的size，表示当前添加数据小于当前的中位数，则实际上的中位数偏向了大顶堆了，所以从大顶堆中取出一个数据作为新的中位数；反之也是这样，从小顶堆中取出一个数据作为新的中位数也是这个道理。如图所示
(4).进一步的调整
如果在(3)中，移除之前，大顶堆的size - 小顶堆的.sze = 1，而且移除的数据在大顶堆中，那么实际的中位数就偏向了小顶堆，所以需要进一步调整；同时如果，本来大顶堆的size 等于 小顶堆的.sze ，而且移除的数据在小顶堆中，那么实际的中位数就偏向大顶堆。
3.代码
说完了解释，现在开始贴代码
public class minComparator implements Comparator<Integer> {
public int compare(Integer a, Integer b) {
if (a > b)
return 1;
else if (a == b)
return 0;
else
return -1;
}
}
public class maxComparator implements Comparator<Integer> {
public int compare(Integer a, Integer b) {
if (a > b)
return -1;
else if (a == b)
return 0;
else
return 1;
}
}
public List<Integer> medianSlidingWindow(int[] nums, int k) {
List<Integer> res = new ArrayList<Integer>();
if (k == 0 || nums.length < k) {
return res;
}
PriorityQueue<Integer> maxQueue = new PriorityQueue<>();//大顶堆
PriorityQueue<Integer> minQueue = new PriorityQueue<>();//小顶堆
int media = nums[0];
//最初的添加数据
for (int i = 0; i < k; i++) {
if (media < nums[i]) {
minQueue.offer(nums[i]);
} else {
maxQueue.offer(nums[i]);
}
if (maxQueue.size() > minQueue.size()) {
minQueue.offer(media);
media = maxQueue.poll();
} else if (maxQueue.size() < minQueue.size() - 1) {
maxQueue.offer(media);
media = maxQueue.poll();
}
}
res.add(media);
//后续的添加数据
for (int i = k; i < nums.length; i++) {
if (media < nums[i]) {
minQueue.offer(nums[i]);
} else {
maxQueue.offer(nums[i]);
}
//移除当前窗口第一个值
int old = nums[i - k];
if (old == media) {
if (minQueue.size() > maxQueue.size()) {
media = minQueue.poll();
} else {
media = maxQueue.poll();
}
} else if (old < media) {
maxQueue.remove(old);
} else {
minQueue.remove(old);
}
//进一步调整
while (maxQueue.size() > minQueue.size()) {
minQueue.offer(media);
media = maxQueue.poll();
}
while (minQueue.size() < minQueue.size() - 1) {
maxQueue.offer(media);
media = minQueue.poll();
}
res.add(media);
}
return res;
}
