## 最小堆 ``` template <typename T> class MinHeap { private: int capacity; int count; vector<T> data; public: // 构造一个空堆, 容量为cap MinHeap(int cap) : capacity(cap), count(0) { data = vector<T>(capacity); } // 通过一个给定数组构建堆, 容量为数组大小n MinHeap(T arr[], int n) : capacity(n), count(n) { data = vector<T>(n); for (int i = 0; i < n; ++i) data[i] = arr[i]; for (int i = ( n - 1) / 2; i >= 0; --i) shift_down(i); } bool empty() const { return count == 0; } void insert(const T& val) { if (count < capacity) { data[count] = val; shift_up(count++); } else { if (data[0] < val) { data[0] = val; shift_down(0); } } } T popMin() { assert(count > 0); T result = data[0]; swap(data[0], data[--count]); shift_down(0); return result; } T getMin() { assert(count > 0); return data[0]; } private: void shift_up(int k) { while (k > 0) { int parent = (k - 1) / 2; if (data[parent] < data[k]) break; swap(data[parent], data[k]); k = parent; } } void shift_down(int k) { while (2 * k + 1 < count) { int min = 2 * k + 1; if (min + 1 < count && data[min + 1] < data[min]) min++; if (data[k] < data[min]) break; swap(data[k], data[min]); k = min; } } }; ```