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;
}