数据结构将序列:7,4,9,15,2,6,10建成堆并输出
时间: 2024-06-16 14:07:47 浏览: 13
要将序列建成堆,可以使用堆排序的思想。堆是一种完全二叉树,分为最大堆和最小堆两种类型。在最大堆中,父节点的值大于等于其子节点的值;在最小堆中,父节点的值小于等于其子节点的值。
以下是将序列建成最大堆的步骤:
1. 首先,将序列依次插入到一个空堆中。
2. 从最后一个非叶子节点开始,向上调整每个节点,使得每个节点满足最大堆的性质。
3. 重复步骤2,直到根节点。
下面是C++代码实现:
```cpp
#include <iostream>
#include <vector>
using namespace std;
// 向下调整函数
void adjustDown(vector<int>& nums, int parent, int len) {
int child = parent * 2 + 1; // 左子节点
while (child < len) {
// 如果右子节点存在且大于左子节点,则选择右子节点
if (child + 1 < len && nums[child] < nums[child + 1]) {
child++;
}
// 如果父节点大于等于子节点,则不需要调整
if (nums[parent] >= nums[child]) {
break;
}
// 交换父节点和子节点的值
swap(nums[parent], nums[child]);
parent = child;
child = parent * 2 + 1;
}
}
// 建堆函数
void buildHeap(vector<int>& nums) {
int len = nums.size();
// 从最后一个非叶子节点开始向下调整
for (int i = len / 2 - 1; i >= 0; i--) {
adjustDown(nums, i, len);
}
}
int main() {
vector<int> nums = {7, 4, 9, 15, 2, 6, 10};
buildHeap(nums);
cout << "建成堆后的序列为:";
for (int num : nums) {
cout << num << " ";
}
cout << endl;
return 0;
}
```
运行结果:
```
建成堆后的序列为:15 7 10 4 2 6 9
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)