编写一个算法,判断一个数据序列是否构成一个小根堆,C++
时间: 2024-04-29 21:26:51 浏览: 114
可以使用以下算法来判断一个数据序列是否构成一个小根堆:
1. 从最后一个非叶子节点开始,往前遍历所有的非叶子节点 i。
2. 对于每个非叶子节点 i,判断它的左右子节点是否比它小,如果是,则不满足小根堆的定义,返回 false。
3. 如果所有的非叶子节点都满足小根堆的定义,返回 true。
以下是用 C 语言实现的代码:
```c
#include <stdbool.h>
bool is_min_heap(int arr[], int n) {
for (int i = (n - 2) / 2; i >= 0; i--) {
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left < n && arr[left] < arr[i]) {
return false;
}
if (right < n && arr[right] < arr[i]) {
return false;
}
}
return true;
}
```
其中,arr 是待判断的数组,n 是数组的长度。函数返回值为 true 表示该数组构成了一个小根堆,返回值为 false 表示不是小根堆。
阅读全文