创建一个最小堆,并可以实现插入删除,请使用C++的类模板完成,并给出主函数
时间: 2024-04-29 22:23:31 浏览: 11
C++代码如下:
```c++
#include<iostream>
#include<vector>
using namespace std;
template<typename T>
class MinHeap {
private:
vector<T> heap;
void siftUp(int i) {
while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
swap(heap[(i - 1) / 2], heap[i]);
i = (i - 1) / 2;
}
}
void siftDown(int i) {
int minIndex = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < heap.size() && heap[l] < heap[minIndex])
minIndex = l;
if (r < heap.size() && heap[r] < heap[minIndex])
minIndex = r;
if (i != minIndex) {
swap(heap[i], heap[minIndex]);
siftDown(minIndex);
}
}
public:
MinHeap() {}
void insert(T val) {
heap.push_back(val);
siftUp(heap.size() - 1);
}
T removeMin() {
T minVal = heap.front();
heap[0] = heap.back();
heap.pop_back();
siftDown(0);
return minVal;
}
bool empty() {
return heap.empty();
}
int size() {
return heap.size();
}
};
int main() {
MinHeap<int> heap;
heap.insert(3);
heap.insert(2);
heap.insert(1);
heap.insert(4);
heap.insert(5);
while (!heap.empty()) {
cout << heap.removeMin() << " ";
}
return 0;
}
```