## 最小索引堆 ``` template <typename T> class IndexMinHeap { private: int capacity; int count; vector<T> data; // 最小索引堆中的数据 vector<int> indexs; // 最小索引堆中的索引, indexes[x] = i 表示索引i在data的位置 public: // 构造一个空堆, 容量为cap IndexMinHeap(int cap) : capacity(cap), count(0) { data = vector<T>(capacity); indexs = vector<int>(capacity); } // 通过一个给定数组构建堆, 容量为数组大小n IndexMinHeap(T arr[], int n) : capacity(n), count(n) { data = vector<T>(n); indexs = vector<int>(n); for (int i = 0; i < n; ++i) { data[i] = arr[i]; indexs[i] = 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; indexs[count] = count; shift_up(count++); } else { if (data[indexs[0]] < val) { data[indexs[0]] = val; shift_down(0); } } } T popMin() { assert(count > 0); T result = data[indexs[0]]; swap(indexs[0], indexs[--count]); shift_down(0); return result; } T getMin() { assert(count > 0); return data[indexs[0]]; } void change(int index, const T& val) { assert(index < count); data[index] = val; for (int i = 0; i < count; ++i) { if (indexs[i] == index) { shift_up(i); shift_down(i); break; } } } private: void shift_up(int k) { while (k > 0) { int parent = (k - 1) / 2; if (data[indexs[parent]] < data[indexs[k]]) break; swap(indexs[parent], indexs[k]); k = parent; } } void shift_down(int k) { while (2 * k + 1 < count) { int min = 2 * k + 1; if (min + 1 < count && data[indexs[min + 1]] < data[indexs[min]]) min++; if (data[indexs[k]] < data[indexs[min]]) break; swap(indexs[k], indexs[min]); k = min; } } }; ```