sort_messed_array.cpp

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

vector<int> sortKMessedArray(const vector<int>& v, int k) {
  auto N = v.size();
  if (N == 0) return {};

  auto compare = [](auto i, auto j) { return i > j; };
  priority_queue<int, vector<int>, decltype(compare)> pq(compare);

  auto p = 0;
  auto q = k;

  for (auto i = p; i <= q; ++i) {
    pq.push(v[i]);
  }

  vector<int> results(N, 0);

  while (!pq.empty()) {
    auto top = pq.top(); pq.pop();

    results[p++] = top;

    if (q < N - 1) {
      pq.push(v[++q]);
    }
  }

  return results;
}

int main() {
  auto results = sortKMessedArray({1, 4, 5, 2, 3, 7, 8, 6, 10, 9}, 2);
  for (auto i : results) {
    cout << i << " ";
  }
}