Algorithm (Heap)

1. Let’s denote the input array by $A$. We maintain a state $S$ of two heaps, one of which is a max heap and the other a min heap. For ease of notation, we denote them by $H_{\min}$ and $H_{\max}.$
2. At any given moment, we ensure the state $S$ adheres to the following invariants:
   1. $A_{m:j}\in H_{\min}$ and $A_{i:m}\in H_{\max}$ and $H_{\min}\cup H_{\max}=A_{i:j}.$
   2. $\mathrm{size}(H_{\min})\geq\mathrm{size}(H_{\max})$ and $|\mathrm{size}(H_{\mathrm{min}})-\mathrm{size}(H_{\max})|\leq1.$
3. Then for any moment, the median of subsequence $A_{i:j}$ is $$\mathrm{median}(A_{i:j})=\begin{cases} \frac{1}{2}(\mathrm{top}(H_{\min})+\mathrm{top}(H_{\max})) & \text{if }j-i+1\text{ is even}\\\\ \mathrm{top}(H_{\min}) & \text{else } \end{cases}$$
4. The problem is then reduced a simple sliding window scan. We skip the details for the implementation.

Code (Cpp17)

class Solution {
 public:
  vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    const struct {
      mutable std::multiset<int, std::less<>> min_heap;
      mutable std::multiset<int, std::greater<>> max_heap;
    } state;

    auto erase_one = [&](auto* s, int key) {
      const auto pos = s->find(key);
      if (pos == std::end(*s))
        return;
      else 
        s->erase(pos);
    };

    auto top = [&](const auto& s) { return *(std::begin(s)); };

    auto query_median = [&]() -> double {
      auto & [min_heap, max_heap] = state;
      if (std::size(min_heap) == std::size(max_heap) + 1)
        return top(min_heap);
      else if (not std::empty(min_heap) and std::size(min_heap) == std::size(max_heap))
        return (double(top(min_heap)) + double(top(max_heap))) / 2.0;
      else
        throw std::domain_error("unimplemented");
    };

    auto ensure_state_invariant = [&] {
      auto & [min_heap, max_heap] = state;
      if (std::size(min_heap) > std::size(max_heap) + 1) {
        max_heap.emplace(top(min_heap));
        erase_one(&min_heap, top(min_heap));
      }
      else if (std::size(min_heap) < std::size(max_heap)) {
        min_heap.emplace(top(max_heap));
        erase_one(&max_heap, top(max_heap));
      }
    };

    auto insert = [&](int x) {
      auto& [min_heap, max_heap] = state;
      if (std::empty(min_heap) or x >= top(min_heap))
        min_heap.insert(x);
      else
        max_heap.insert(x);
      ensure_state_invariant();
    };

    auto remove = [&](int x) {
      auto& [min_heap, max_heap] = state;
      if (top(min_heap) > x)
        erase_one(&max_heap, x);
      else
        erase_one(&min_heap, x);
      ensure_state_invariant();
    };

    const auto solution = [&] {
      const struct {
        mutable std::deque<int> data;
        mutable std::vector<double> acc;
      } window;

      auto emplace_back = [&](int x) -> void {
        auto& [data, acc] = window;
        data.emplace_back(x);
        insert(x);
        if (std::size(window.data) == k)
          acc.emplace_back(query_median());
        else if (std::size(window.data) == k + 1) {
          remove(window.data.front());
          window.data.pop_front();
          acc.emplace_back(query_median());
        }
      };

      for (const auto x : nums)
        emplace_back(x);

      return window.acc;
    }();

    return solution;
  }
};