Sliding Window Median

Given an array of n integer, and a moving window(size k), move the window at each iteration from the start of the array, find the median of the element inside the window at each moving. (If there are even numbers in the array, return the N/2-th number after sorting the element in the window. )

Key Points:

1. Maintain two heaps:

maxHeap (save 1st half) 
minHeap (save 2nd half)
with a **Adam Rule** "heap A size = heap B size" or  "heap A size + 1 = heap B size"

2. Insert:

1. compare the insert value and relate heap's threshold, find target heap
2. insert value to target heap.

3.Delete:

Use default API will cost **O(n)**
>> map::erase(v)                 C++
>> PriorityQueue::remove(v)      Java

4.Adjust:

Adjust the two heaps with **Adam Rule**, keep them balance.

5.Record:

Record current status:  Median

public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
    ArrayList<Integer> result = new ArrayList<>();
    if (nums == null || nums.length == 0 || k == 0) {
      return result;
    }
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, Collections.reverseOrder());
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int i = 0; i < nums.length; i++) {
      // add new element into one of the heap
      if (maxHeap.isEmpty() || nums[i] < maxHeap.peek()) {
        maxHeap.offer(nums[i]);
      } else {
        minHeap.offer(nums[i]);
      }
      // remove element outside of window
      if (i >= k) {
        if (nums[i - k] <= maxHeap.peek()) {
          maxHeap.remove(nums[i - k]);
        } else {
          minHeap.remove(nums[i - k]);
        }
      }
      // balance two heaps, make sure maxHeap contains one more element if k is odd.
      while (minHeap.size() >= maxHeap.size() + 1) {  
        maxHeap.offer(minHeap.poll());
      }
      while (maxHeap.size() > minHeap.size() + 1) {
        minHeap.offer(maxHeap.poll());
      }
      // add result
      if (i >= k - 1) {
        result.add(maxHeap.peek());
      }
    }
    return result;
  }