Heap

template <typename Compare>
class Heap {
 public:
  explicit Heap(int capacity = 16) : compare(Compare()) {
    numVec.reserve(capacity + 1);
    numVec.emplace_back();
  }
  // 堆中的元素个数
  inline int size() const { return numVec.size() - 1; }
  // 堆是否为空
  inline int empty() const { return size(); }
  // 堆顶
  inline int top() const { return numVec[1]; }
  // 加入堆, 时复O(log(n))
  void pushHeap(int num) {
    numVec.push_back(num);
    up(size());
  }
  // 弹出堆顶元素, 时复O(log(n))
  void popHeap() {
    numVec[1] = numVec[size()];
    numVec.pop_back();
    down(1, size());
  }
  // 生成堆, 时复O(n)
  void makeHeap() {
    const int n = size();
    for (int i = n >> 1; i; --i) {
      down(i, n);
    }
  }
  // 检查是否是堆, 时复O(n)
  bool checkHeap() const {
    const int n = size();
    int parent = 1;
    for (int i = 2; i <= n; ++i) {
      if (compare(numVec[i], numVec[parent])) {
        return false;
      }
      if (i & 1) {
        ++parent;
      }
    }
    return true;
  }
  // 堆排序: 小根堆,从大到小排序; 大根堆,从小到大排序, 时复O(n*log(n))
  void sortHeap() {
    int n = size();
    while (n > 1) {
      swap(numVec[1], numVec[n]);
      --n;
      down(1, n);
    }
  }
  // 加入末尾, pushBack后checkHeap返回false
  inline void pushBack(int num) { numVec.push_back(num); }
  inline int operator[](int index) const { return numVec[index + 1]; }
  void print() {
    const int n = size();
    for (int i = 1; i <= n; ++i) {
      printf("%d ", numVec[i]);
    }
    puts("");
  }

 private:
  void up(int i) {
    while (i > 1) {
      const int parent = i >> 1;
      if (!compare(numVec[i], numVec[parent])) {
        break;
      }
      swap(numVec[i], numVec[parent]);
      i = parent;
    }
  }
  void down(int i, int n) {
    for (;;) {
      int j = i;
      const int left = i << 1;
      if (left <= n && compare(numVec[left], numVec[j])) {
        j = left;
      }
      const int right = left + 1;
      if (right <= n && compare(numVec[right], numVec[j])) {
        j = right;
      }
      if (i == j) {
        break;
      }
      swap(numVec[i], numVec[j]);
      i = j;
    }
  }
  const Compare compare;
  vector<int> numVec;
};

main

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
  int n, m, x;
  scanf("%d%d", &n, &m);
  Heap<greater<int>> heap(m);
  for (int i = 0; i < m; ++i) {
    scanf("%d", &x);
    heap.pushBack(x);
  }
  heap.makeHeap();
  for (int i = m; i < n; ++i) {
    scanf("%d", &x);
    if (heap.top() > x) {
      heap.popHeap();
      heap.pushHeap(x);
    }
  }
  heap.sortHeap();
  heap.print();
  return 0;
}