输入格式: • 第一行有一个整数m (m<=10000) • 以下m行每行描述一个命令 • 命令格式1 x 表示Insert(int val)。 (将x插入堆,val范围(0-10000)) • 命令格式2 表示Delete_Min。 (删除堆顶元素) • 命令格式3 i 表示Delete(int i). (删除堆中第i个元素) • 命令格式4 ix 表示Decrease_Value(int i, int val)(减少堆中第i个元素的 值,令其为x,并向上调整从而满足堆要求,val范围(0-10000)) • 输出格式:输出最后一步操作后的堆排序结果
时间: 2024-02-27 20:57:30 浏览: 22
好的,我已经了解了您的问题。这是一道关于堆的问题,需要对堆进行插入、删除、减少值等操作,并输出最后的堆排序结果。我会为您解答这个问题,以下是我的解法:
首先,我们需要定义一个堆的数据结构,包括堆的大小、堆的元素数组等。其中,堆的元素数组可以使用vector<int>来实现。代码如下:
```cpp
struct Heap {
int size;
vector<int> arr;
Heap() {
size = 0;
arr.resize(1);
}
};
```
接下来,我们需要实现堆的插入操作。插入操作需要将元素插入堆的末尾,并向上调整,使得堆满足堆的性质。具体实现如下:
```cpp
void Insert(Heap& heap, int val) {
heap.arr.push_back(val);
heap.size++;
int cur = heap.size;
while (cur > 1 && heap.arr[cur] < heap.arr[cur / 2]) {
swap(heap.arr[cur], heap.arr[cur / 2]);
cur /= 2;
}
}
```
然后,我们需要实现堆的删除操作。删除操作需要将堆顶元素删除,并将堆的最后一个元素放到堆顶,并向下调整,使得堆满足堆的性质。具体实现如下:
```cpp
void Delete_Min(Heap& heap) {
if (heap.size == 0) return;
heap.arr[1] = heap.arr[heap.size];
heap.arr.pop_back();
heap.size--;
int cur = 1;
while (cur * 2 <= heap.size) {
int child = cur * 2;
if (child + 1 <= heap.size && heap.arr[child + 1] < heap.arr[child]) child++;
if (heap.arr[child] < heap.arr[cur]) {
swap(heap.arr[child], heap.arr[cur]);
cur = child;
} else {
break;
}
}
}
```
接下来,我们需要实现堆的删除指定位置元素的操作。删除指定位置元素的操作需要将指定位置元素删除,并将堆的最后一个元素放到指定位置,并向上或向下调整,使得堆满足堆的性质。具体实现如下:
```cpp
void Delete(Heap& heap, int i) {
if (i > heap.size) return;
heap.arr[i] = heap.arr[heap.size];
heap.arr.pop_back();
heap.size--;
if (i == heap.size + 1) return;
if (i == 1 || heap.arr[i] >= heap.arr[i / 2]) {
int cur = i, child = cur * 2;
while (child <= heap.size) {
if (child + 1 <= heap.size && heap.arr[child + 1] < heap.arr[child]) child++;
if (heap.arr[child] < heap.arr[cur]) {
swap(heap.arr[child], heap.arr[cur]);
cur = child;
child = cur * 2;
} else {
break;
}
}
} else {
int cur = i;
while (cur > 1 && heap.arr[cur] < heap.arr[cur / 2]) {
swap(heap.arr[cur], heap.arr[cur / 2]);
cur /= 2;
}
}
}
```
最后,我们需要实现堆的减少值操作。减少值操作需要将指定位置元素的值减小,并向上调整,使得堆满足堆的性质。具体实现如下:
```cpp
void Decrease_Value(Heap& heap, int i, int val) {
if (i > heap.size) return;
heap.arr[i] = val;
int cur = i;
while (cur > 1 && heap.arr[cur] < heap.arr[cur / 2]) {
swap(heap.arr[cur], heap.arr[cur / 2]);
cur /= 2;
}
}
```
最后,我们只需要按照题目要求进行操作,最后输出堆排序结果即可。完整代码如下: