写一个有效的算法来测试一个给定的数组A[1...n]是否是一个堆，该算法的时间复杂性是多少？

Question

写一个有效的算法来测试一个给定的数组A[1...n]是否是一个堆，该算法的时间复杂性是多少？

Answer 1

时间复杂度是O(n)，可以从n到1，也可以从1到n，从n开始就看(k/2)下取整下标的元素（也就是堆中的双亲）是否满足大根或者小根的条件，从1开始就看2k和2k+1下标的元素（就是堆中的左右孩子）是否满足堆的条件

Answer 2

//复杂度O(n)
//大根堆
bool isHeap(int data, int n) {
int i, j, k;
for(i = 0, j = 1;j < n;i++, j = 2*i+1) {
k = data[j];
if(j+1 < n && data[j+1] > data[j]) k = data[j+1];
if(data[i] < k) return false;
}
return true;
}

//小根堆
bool isHeap(int data, int n) {
int i, j, k;
for(i = 0, j = 1;j < n;i++, j = 2*i+1) {
k = data[j];
if(j+1 < n && data[j+1] < data[j]) k = data[j+1];
if(data[i] > k) return false;
}
return true;
}